## Microsoft Jane Street Interview Question

Software Engineer / Developers- 0of 0 votes
Reverse a linked list using recursion

Above code skips last element, following is the working with little modification

```
void LinkedList::Reverse(Node* root, Node* prev)
{
if(root->next == NULL)
{
this->list = root;
this->list->next = prev;
return;
}
Reverse(root->next, root);
root->next = prev;
}
```

// Simple Solution without confusion

/* Let j be pointer to 1st node of list then initial call ll be list_rec_reverse(&j, NULL, j) */

void list_rec_reverse(list **l, list *prev, list *curr)

{

if(NULL == curr)

{

*l=prev;

return;

}

list_rec_reverse(l,curr,curr->next);

curr->next = prev;

}

1) use a recursive function that provides sublist tail as result (and updates head as side-effect)

2) use two references to adjacent nodes (current and previous), chain current.next to previous

```
public class ReverseLinkedList {
private class Node {
private int value;
private Node next;
public Node(int value){
this.value = value;
}
public int getValue(){ return value;}
public Node getNext(){ return next;}
public void setNext(Node next){ this.next = next;}
}
private Node head;
public ReverseLinkedList(){
}
public void add(int v){
Node n = new Node(v);
n.setNext(head);
head = n;
}
public int remove(){
if( null == head){
throw new IllegalStateException("can't remove from empty list");
}
int v = head.getValue();
head = head.getNext();
return v;
}
public void reverse(){
if( null != head ){
Node newTail = reverseSubList(head);
newTail.setNext(null);
}
}
public void reverse2(){
if( null != head ){
Node previous = head;
Node n = head.getNext();
head.setNext(null);
while( null != n ){
Node oldNext = n.getNext();
n.setNext(previous);
previous = n;
n = oldNext;
}
head = previous;
}
}
public void print(){
Node n = head;
while( null != n ){
System.out.print(n.getValue());
System.out.print(" -> ");
n = n.getNext();
}
System.out.print("null");
}
// n is sublist head
// return sublist tail once reversed
// updates head reference when needed
private Node reverseSubList(Node n){
if( null == n.getNext()){
head = n;
} else {
Node subListTail = reverseSubList(n.getNext());
subListTail.setNext(n);
}
return n;
}
public static void main(String[] args){
ReverseLinkedList list = new ReverseLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.print();
list.reverse();
list.print();
list.reverse2();
list.print();
}
}
```

```
public class node
{
public object data;
public node next;
public node()
{
data = null;
next = null;
}
public node(object item)
{
data = item;
next = null;
}
}
public class LinkList
{
private node List;
public int count=0;
public LinkList()
{
List = null;
}
public void AddNode(object item)
{
if (List == null)
{
List = new node(item);
count++;
}
else
{
node temp = new node(item);
node p = List;
while (p.next != null)
{
p = p.next;
}
p.next = temp;
count++;
if (count%1000 == 0)
Console.WriteLine(count);
}
}
public void Revese()
{
node cur, prev=null, l;
if (List !=null)
l = List;
else
return;
while (l != null)
{
cur = l;
l = l.next;
cur.next = prev;
prev = cur;
}
List = prev;
}
}
```

C# version reverse linked list using recursion

```
Node reverseRecurse(Node prev, Node cur)
{
if(cur==null) return cur;
Node head;
//recursion first
if(cur.next!=null)
head=reverseRecurse(cur,cur.next);
else
head=cur;
//revert pointer
cur.next=prev;
//handle last level recursion
return head;
}
main()
{
Node list;
list = reverseRecurse(null, list);
}
```

If there are no restrictions on memory usage, you can use an external stack.

func reverseLinkedList(Node *head)

Node temp = head

while (temp!= NULL)

Stack.push(temp->data)

temp=temp->next;

//Now pop the elements back. you have it in the reverse order

while(Stack.isEmpty)

Node node

if(!head)

head = node

head->next = NULL

else

node->data = pop()

node->next = head

head = node

return head

I haven't done error correction, but the iterative code would be some what like above.

You can also have a recursive version in a similar fashion.

void reverse_LL(*root, *head)

{

if(root == NULL || root->next == NULL)

{

head = root;

return;

}

if(root->next->next == NULL)

{

head = root->next;

root->next->next = root;

root->next = NULL;

return;

}

reverse(root->next, head);

root->next->next = root;

root->next = NULL;

return;

}

I don't think "if(root->next->next == NULL)" is necessary, since you already considered when root->next == NULL.

so the code would be:

void reverse_LL(*root, *head)

{

if(root == NULL || root->next == NULL)

{

head = root;

return;

}

reverse(root->next, head);

root->next->next = root;

root->next = NULL;

}

the version by euv921, modify to,

// root is the original head, head is the new head of the list.

void reverse_LL(Node ** root, Node** head)

{

if(root == NULL || (*root)->next == NULL)

{

*head = *root;

return;

}

reverse_LL(&(*root)->next, head);

(*root)->next->next = *root;

(*root)->next = NULL;

};

help other engineers to save time ......

// my version, works, //

void reverseList( Node ** pphead)

{ if(!*pphead) return;

Node * tmp;

Node* current;

Node * result = NULL;

current = *pphead;

while(current)

{ tmp = current->next;

current->next = result;

result = current;

current = tmp; }

*pphead = result;

};

void reverseListRecur( Node ** pphead)

{ if(!pphead||!*pphead||!(*pphead)->next) return;

Node * first = *pphead;

Node* rest = first->next;

reverseListRecur(&rest);

first->next->next = first;

first->next = NULL;

*pphead = rest;

};

It would mostly work... I hope ;)

```
node* reverse(node* head)
{
node* temp;
if(!head) // If empty list, empty list would be the result
return NULL;
if(!head->next) // If it is a single node or last node,
return head; //it would again be the reversed one
temp = reverse(head->next); // Reverse the remaining part of the list
head -> next -> next = head; // Come back, and reverse the link between the nodes
head -> next = NULL; // This is just a case for the head of the list
return temp; // Returns the head of the reversed linked list
}
```

//Create a class Node

public class Node {

String key;

public String getKey() {

return key;

}

public void setKey(String key) {

this.key = key;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

Node next ;

}

//Create a Singly Linked List

public class LinkedList {

Node HEAD;

Node TAIL;

public LinkedList(Node HEAD,Node TAIL) {

this.HEAD = HEAD;

this.TAIL = TAIL;

}

public void traveseList(){

Node n = this.HEAD;

while(n != null){

System.out.println("Value at Node::" + n.getKey());

n = n.getNext();

}

}

public void reverseList(){

Node n,n1,n2;

n = this.HEAD;

n1 = n.getNext();

n2 = n1.getNext();

this.TAIL = n;

n.setNext(null);

while(n1.getNext() != null){

n1.setNext(n);

n = n1;

n1 = n2;

n2 = n2.getNext();

}

n1.setNext(n);

this.HEAD = n1;

}

public static void main(String[] args) {

Node n1 = new Node();

Node n2 = new Node();

Node n3 = new Node();

Node n4 = new Node();

Node n5 = new Node();

Node n6 = new Node();

n1.setKey("JAVA");

n2.setKey("RUBY");

n3.setKey("HTML");

n4.setKey("C++");

n5.setKey("C");

n6.setKey("Obj C");

n1.setNext(n2);

n2.setNext(n3);

n3.setNext(n4);

n4.setNext(n5);

n5.setNext(n6);

n6.setNext(null);

LinkedList list = new LinkedList(n1, n6);

list.traveseList();

list.reverseList(); // Reverse the list

System.out.println("Revers List...");

list.traveseList();

}

}

```
node *rev(node *root)
{
node *rev = NULL;
node *temp = root;
while (temp){
node *current = temp->next;
temp->next = rev;
rev = temp;
temp = current;
}
return rev;
}
node *rev(node *root)
{
if (!root)
return NULL;
node *head = rev(root->next);
root->next->next = root;
root->next = NULL;
return head;
}
```

```
node *rev(node *root)
{
node *rev = NULL;
node *temp = root;
while (temp){
node *current = temp->next;
temp->next = rev;
rev = temp;
temp = current;
}
return rev;
}
node *rev(node *root)
{
if (!root)
return NULL;
node *head = rev(root->next);
root->next->next = root;
root->next = NULL;
return head;
}
```

Solution:

```
public void ReverseList()
{
Node loop = Head;
Node reverse = null;
Node temp = null;
Console.Clear();
Console.WriteLine("\nOriginal List.....");
DisplayList();
while (loop != null)
{
temp = loop.Next;
loop.Next = reverse;
reverse = loop;
loop = temp;
}
Head = reverse;
Console.WriteLine("\nReversed List....");
DisplayList();
```

}

- S February 21, 2011