Reverse Linked List

Problem

Reverse a linked list.

OR

Given the head of a singly linked list, reverse the list, and return the reversed list.

Follow ups

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

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

Examples

Example 1

graph TB;
	classDef royalBlueNode fill:#4169E1, color:#ffffff, stroke:#ffffff, stroke-width:1px;
	linkStyle default stroke:#FFD700, stroke-width:2px;
	subgraph G1[" "]
	   A(1):::royalBlueNode --- B(2):::royalBlueNode --- C(3):::royalBlueNode --- D(4):::royalBlueNode --- E(5):::royalBlueNode --- K("NULL")
	end
	
	subgraph G2[" "]
	   F(5):::royalBlueNode --- G(4):::royalBlueNode --- H(3):::royalBlueNode --- I(2):::royalBlueNode --- J(1):::royalBlueNode --- L("NULL")
	end
	
	
G1 --- G2	

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

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.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/D9BwI7iyo2s" frameborder="0" allowfullscreen></iframe></div>

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

Java

class Solution {
	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;
	}
}

Python

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev: Optional[ListNode] = None
        curr: Optional[ListNode] = head
        
        # Traversing the list
        while curr:
            nxt: Optional[ListNode] = curr.next  # Backup reference to the next node
            curr.next = prev  # Reverse the link
            prev = curr  # Move prev to the current node
            curr = nxt  # Move curr to the next node
        
        return prev

Dry Run - Visualization

Method 2 - 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

Java

class Solution {
    public ListNode reverseList(ListNode head) {
        // Edge case: Empty list
        if (head == null) {
            return null;
        }
        
        // Call the recursive helper function
        return helper(null, head);
    }

    protected ListNode helper(ListNode prev, ListNode curr) {
        // Base case: If curr becomes null, prev is the new head of the reversed list
        if (curr == null) {
            return prev;
        }
        
        // Backup the next node before breaking the link
        ListNode next = curr.next;
        
        // Reverse the link
        curr.next = prev;
        
        // Recur for the rest of the list
        return helper(curr, next);
    }
}

Python

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Edge case: Empty list
        if not head:
            return None
        
        # Start the recursive process with prev = None and curr = head
        return self._helper(None, head)
    
    def _helper(self, prev: Optional[ListNode], curr: Optional[ListNode]) -> Optional[ListNode]:
        # Base case: If curr is None, prev is the new head
        if not curr:
            return prev
        
        # Backup the next node before breaking the link
        nxt = curr.next
        
        # Reverse the current node's link
        curr.next = prev
        
        # Recur for the rest of the list
        return self._helper(curr, nxt)

Complexity

• ⏰ Time complexity: O(n), to process each node and reverse the links.
• 🧺 Space complexity: O(n), due to the recursive call stack, which will use memory equivalent to the depth of the recursion.

Method 3 - 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

Java

class Solution {
    public ListNode reverseList(ListNode head) {
        // Base case: if the list is empty or has only one node, return the head
        if (head == null || head.next == null) {
            return head;
        }
        
        // Recursive call to reverse the rest of the list
        ListNode newHead = reverseList(head.next);
        
        // Reverse the link
        head.next.next = head;
        head.next = null;
        
        // Return the head of the reversed list
        return newHead;
    }
}

Python

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base case: if the list is empty or has only one node, return the head
        if not head or not head.next:
            return head
        
        # Recursive call to reverse the rest of the list
        new_head = self.reverseList(head.next)
        
        # Reverse the link
        head.next.next = head
        head.next = None
        
        # Return the head of the reversed list
        return new_head

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n)

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,

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 xo

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