Leetcode — 206. Reverse Linked List (Iteration and Recursion included)

The link to the problem: https://leetcode.com/problems/reverse-linked-list/

For example, the original linked list is 1->2->3->4->5 ->null
and we want to get the result linked list like 5->4->3->2->1->null

I was actually writing the story of how to solve 92. Reverse Linked List II and just want to briefly mention how to reverse a linked list.
However, I found it hard to let people understand the idea if this is their first time to solve this type of problem.

I’m also not good at these types of questions, so I will try to write the process as clear as possible. 😃

The problem might be a lot easier if this is a double linked list.
In this case, we only know who the node “points to” without knowing “who” points to the current node.
Hence, we need to have a “pre” that represents the previous node of this current node.
The code is only a few lines but it might take some time to understand:

public ListNode reverseList(ListNode node) {
        ListNode pre = null;
        ListNode cur = node;
        while(cur!=null)
        {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

Our goal is to keep switching pre and cur, so in the end:
1. pre will be the head of our reversed list
2. cur will be null
3. node, i.e. our original head, will be the end of the reversed list that points to cur.

Let’s see an example and know the idea clearly!
In the beginning, node = 1->2->3->4->5 ->null

Step 0. pre = null, cur = 1->2->3->4->5 ->null
- cur represents the current node we are going to reverse.
(i.e., we want to break the bond of the current node and its next node or we can say we want to let cur becomes the HEAD of PRE)
- pre represents the previous node in front of the current node to which we want to let cur point right now.

Step 1. cur is not null, so we go into the loop
- We assign next = 2->3->4->5 ->null
- Let cur points to its previous node: cur = 1->null
- Assign cur to pre: pre = 1->null
- Assign next to cur: cur = 2->3->4->5->null

Step 2. cur is not null, so we continue
- Assign next = 3->4->5->null
- Let cur points to pre: cur = 2->1->null
- Assign cur to pre: pre = 2->1->null
- Assign next to cur: cur = 3->4->5->null

Step 3. cur is not null, continue
- Assign next = 4->5->null
- Let cur points to pre: cur = 3->2->1->null
- Assign cur to pre: pre = 3->2->1->null
- Assign next to cur: cur = 4->5->null

Step 4. cur is not null, continue
- Assign next = 5->null
- Let cur points to pre: cur = 4->3->2->1->null
- Assign cur to pre: pre = 4->3->2->1->null
- Assign next to cur: cur = 5->null

Step 5. cur is not null, continue (we are almost there! 👊 )
- Assign next = null
- Let cur points to pre: cur = 5->4->3->2->1->null
- Assign cur to pre: pre = 5->4->3->2->1->null
- Assign next to cur: cur = null

Step 6. cur is null, and we’re done!

The time complexity of this method will be O(n).
The space complexity is O(1). ✌️

After knowing the idea of how to do it iteratively, let’s see how we can solve the problem recursively.

The idea is still similar to the idea of how we do it iteratively. When we want to reverse a linked list recursively, we also need to pass the previous node to it so we can always let the current pointer point to its previous node.

The code will be like below —

public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null)
            return head;
        return helper(null,head);
    }
    public ListNode helper(ListNode pre, ListNode cur){
        if(cur==null)
            return pre;
        ListNode next = cur.next;
        cur.next = pre;
        
        return helper(cur, next);
    }

We always do three things in the helper method

1. Get the next node of the current node.
2. Let cur points to its previous node, instead of the next node.
3. Keep passing “current node (as pre) and next node (as cur)” to reverse those two nodes until there’s no node to reverse. Finally, we will just return the previous node.
   ⚠️ You should know that the input variable pre is currently the head of the reversed list. We will always make cur as pre’s head in the helper method.