Problem

Reverse a linked list.

Follow up 1 - Do it in-place and in one-pass.

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

Examples

For example:

1
2

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Solution

This is one of the famous interview question - can be solved iteratively and recursively. It becomes tricky, as in LinkedList we can go in forward direction. So, we need to understand some pointer basics when traversing and reversing the list.

Method 1 - Iterative Approach Using 3 Pointers and Variables

Algorithm

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

Requires 3 temp variables.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public ListNode reverseList(ListNode head) {
	ListNode prev = null;
	ListNode curr = head;
	
	while (curr != null) {
		ListNode nxt = curr.next;
		curr.next = prev;
		prev = curr;
		curr = nxt;
	}
	
	return prev;
}

Dry Run - Visualization

Method 2 - Recursive Solution Using 1 Pointers

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

Algorithm

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

Visualization - Dry Run

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

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

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

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

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

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

	// Now we join both the lists
	second.next = head;

	return revNode;
}

Method 3 - Recursive Approach Passing 2 Pointers to Function

Another way is we can take 2 pointers - current ascurr and previous as prev. In each recursive call, we will keep on updating curr to curr.next, and prev as well. At the end of recursion, we will set curr.next = prev.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public ListNode reverseList(ListNode head) {
	return reverse(head, null);
}
private ListNode reverse( ListNode curr, ListNode prev) {
    ListNode temp;
    if(curr.next == null) {
        curr.next = prev;
        return head;
    } else {
        temp = reverse(curr.next, curr);
        curr.next = prev;
        return temp;
    }
}

Method 4 - Iteratively using Xor Approach

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

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

1
2
3

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

fastest way is to write it in one line

1

a = a ^ b ^ (b=a)

Similarly, using two swaps

1
2

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

solution using xo

1
2
3
4

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

Solution in one line

1
2
3

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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;
}