Reverse a linked list

Problem

Reverse a linked list.

Follow up - Can you do it with only 2 pointers.

Solution

This is one of the famous interview questions.

Following are two procedures to reverse a single linked list:

• Iterative Procedure
• Recursive Procedure

Iterative solution

Method 1 - Iterative Procedure
The following are the sequence of steps to be followed:

• Initially take three pointers: PrevNode, CurrNode, NextNode
• Let CurrNode point to HeaderNode of the list. And let PrevNode and NextNode points to null
• Now iterate through the linked list until CurrNode is null
• In the loop, we need to change NextNode to PrevNode, PrevNode to CurrNode and CurrNode to NextNode

Consider the following linked list that needs to be reversed:

Taking 3 pointers: PrevNode, CurrNode and NextNode where CurrNode pointing to HeaderNode

After First Iteration:
After the first iteration of the loop, PrevNode points to the node containing element 1 and CurrNode & NextNode points to the node containing element 2. And the node pointed by PrevNode gets unlinked.

After Second Iteration:
After the second iteration of the loop, PrevNode Points to the node containing element 2 and CurrNode & NextNode point to the node containing element 3. And the CurrNode next would be pointing to PrevNode.

 

By the end of the iteration, PrevNode contains the reverse of the complete list.

 Requires 3 temp variables.

public ListNode reverseList(ListNode headerNode)   {
        ListNode prevNode = null;
        ListNode currNode = headerNode;
        ListNode nextNode = null;

        while (currNode != null)
        {
            nextNode = currNode.next;
            currNode.next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
        }

        return prevNode;
  }

Recursive solution 

The following are the sequence of steps to be followed:

• If the list is empty, then the reverse of the list is also empty
• If the list has one element, then the reverse of the list is the element itself
• If the list has n elements, then the reverse of the complete list is reverse of the list starting from second node followed by the first node element. This step is recursive step

The above mentioned steps can be described pictorially as shown below:

Consider the following linked list that needs to be reversed:

Dry run for the above example:

Take a pointer called SecondElementNode, which points to the second element of the list. Here the SecondElementNode points to 2.

Now we need to unlink the node pointed by HeaderNode. This step is to avoid cycle.

Reverse the list pointed by SecondElementNode recursively.

Now we have to append unlinked HeaderNode to the reversed list.

Code for the above solution:
Method 1 - Passing only 1 pointer to function

public ListNode reverseList(ListNode headerNode)
    {
        //  Reverse of a empty list or null list is null
        if (headerNode == null)
        {
            return null;
        }

        //  Reverse of a single element list is the list with that element
        if (headerNode.next == null)
        {
            return headerNode;
        }

        //  Reverse of n element list is reverse of the second element followed by first element

        //  Get the list node pointed by second element
        ListNode secondElementNode = headerNode.next;

        //  Unlink the first element
        headerNode.next = null;

        //  Reverse everything from the second element
        ListNode revNode = reverseList(secondElementNode);

        // Now we join both the lists
        secondElementNode.next = headerNode;

        return revNode;
    }

 Method 2 - Passing 2 pointers to function

node * reverse( Node * ptr , Node * previous)
{
    Node * temp;
    if(ptr->next == NULL) {
        ptr->next = previous;
        return ptr;
    } else {
        temp = reverse(ptr->next, ptr);
        ptr->next = previous;
        return temp;
    }
}
reversedHead = reverse(head, NULL);

I personally prefer the non-recursive solution but it is always good to know both of them.

Follow Up - Can we reverse the list using 2 pointers

Generally, students usually go for recursion when they hear such question of optimizing variables. Of course method 1 of recursive method will work.

Well this can be done iteratively. However few special conditions need to be taken in mind.

Algorithm:

void reverse(Node head) {
    // curNode traverses the list, head is reset to empty list.
    Node curNode = head, *nxtNode;
    head = NULL;

    // Until no more in list, insert current before head and advance.
    while (curNode != NULL) {
        // Need to save next node since we're changing the current.
        nxtNode = curNode.next;

        // Insert at start of new list.
        curNode.next = head;
        head = curNode;

        // Advance to next.
        curNode = nxtNode;
    }
}

xor approach
Another approach is to use xor approach, which is mentioned here.

To swap two variables without the use of a temporary variable,

a = a xor b
b = a xor b
a = a xor b

fastest way is to write it in one line

a = a ^ b ^ (b=a) 

Similarly, using two swaps

swap(a,b)
swap(b,c) 

solution using xor

a = a^b^c
b = a^b^c
c = a^b^c
a = a^b^c 

solution in one line

c = a ^ b ^ c ^ (a=b) ^ (b=c)
b = a ^ b ^ c ^ (c=a) ^ (a=b)
a = a ^ b ^ c ^ (b=c) ^ (c=a) 

The same logic is used to reverse a linked list.

List* reverseList(List *head)
{
 p=head;
 q=p->next;
 p->next=NULL;
 while(q)
 {
    q = (List*) ((int)p ^ (int)q ^ (int)q->next ^ (int)(q->next=p) ^ (int)(p=q));
 }
 head = p;
 return head;
}