reverse-linked-list

Reversing a singly linked list with iteration is not hard, but the recursive solution is a bit tricky. If we add more difficulty and only reverse part of a linked list, can you solve it with both iteration and recursion? Going further, if you need to reverse the list in groups of k, how would you handle that?

This article will go from easy to hard and solve these linked list problems step by step. I will use both recursive and iterative methods, and use visual panels to help you understand. This will strengthen your recursive thinking and your skill in operating linked list pointers.

Reverse the entire singly linked list

On LeetCode, the common structure of a singly linked list is like this:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

Reversing a singly linked list is a basic algorithm problem. LeetCode 206 “Reverse Linked List” is exactly this problem:

LeetCode 206. Reverse Linked List

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

Example 1:**

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

Example 2:**

**Input:** head = [1,2]
**Output:** [2,1]

Example 3:**

**Input:** head = []
**Output:** []

Constraints:

• The number of nodes in the list is the range [0, 5000].

• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Now let’s try several methods to solve this problem.

Iterative solution

The standard way to solve this problem is the iterative solution. We operate several pointers to reverse the direction of each node’s next pointer. There is no big difficulty, the key is to handle pointer details correctly.

Here is the code. With the comments and the visual panel, it should be easy to understand:

class Solution {
    // Reverse the linked list starting from head
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // Due to the structure of a singly linked list, at least three pointers are needed to complete the iterative reversal
        // cur is the current node being traversed, pre is the predecessor node of cur, nxt is the successor node of cur
        ListNode pre, cur, nxt;
        pre = null; cur = head; nxt = head.next;
        while (cur != null) {
            // Reverse each node
            cur.next = pre;
            // Update pointer positions
            pre = cur;
            cur = nxt;
            if (nxt != null) {
                nxt = nxt.next;
            }
        }
        // Return the head node after reversal
        return pre;
    }
}

You can open the visual panel below, and click the line cur.next = pre many times. Then you can clearly see the reversing process of the singly linked list:

::: tip Small tips for pointer operations

The logic of the code above is not complicated, and there is more than one correct way to write it. But when working with pointers, there are some very basic and simple tips that can make your thinking clearer:

1. Once you see an operation like nxt.next, you should immediately think: first check whether nxt is null, otherwise you may get a null pointer exception.

2. Pay attention to the loop end condition. You must know where each pointer is when the loop ends. Then you can return the correct answer. If you feel it is complicated, draw the simplest case and run the algorithm by hand. For example, in this problem you can draw a list with only two nodes 1->2. Then you can figure out exactly where each pointer is when the loop finishes.

:::

Recursive Solution

The iterative solution above is a bit tedious because of pointer operations, but the idea is still clear. Now, what if you are asked to reverse a singly linked list using recursion? Do you have any ideas?

For beginners, it might be hard to think of a recursive way. That is normal. If you learn the way of thinking in binary tree algorithms later, you may be able to come up with this algorithm yourself.

A binary tree is actually an extension of a singly linked list—it's like a "binary linked list". So the recursive thinking for binary trees also works for linked lists.

The key to reversing a linked list recursively is that this problem has a subproblem structure.

For example, suppose you have a singly linked list 1->2->3->4 with 1 as the head. If you ignore the head node 1 and just look at the sublist 2->3->4, it is still a singly linked list, right?

So, your reverseList function should be able to reverse any linked list given as input. Can you use this function to reverse the sublist 2->3->4 first, and then think about how to attach 1 to the end of the reversed list 4->3->2? This way, you will finish reversing the whole list.

reverseList(1->2->3->4) = reverseList(2->3->4) -> 1

This is the idea of "breaking down the problem". Using the definition of the recursive function, we break the original problem into smaller, similar subproblems, and then combine their results to solve the original problem.

There will be special chapters and exercises about this idea later, so we won’t go into more detail here.

Let's look at the code for recursively reversing a singly linked list:

class Solution {
    // Definition: Input the head node of a singly linked list, reverse the list, and return the new head node
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverseList(head.next);
        /**<extend up -200>
        ![](../pictures/reverse-linked-list/3.jpg)
        */
        head.next.next = head;
        /**<extend up -200>
        ![](../pictures/reverse-linked-list/4.jpg)
        */
        head.next = null;
        /**<extend up -200>
        ![](../pictures/reverse-linked-list/5.jpg)
        */
        return last;
    }
}

This algorithm often shows the beauty and cleverness of recursion. Next, let's explain this code in detail. We will also provide a visual panel so you can explore the recursion yourself.

For recursive algorithms that "break down the problem", the most important thing is to be clear about the definition of the recursive function. Specifically, our reverseList function is defined as:

Given a node head, reverse the list starting from head and return the new head of the reversed list.

Once you understand the function definition, let's look at the problem. For example, we want to reverse this list:

When you call reverseList(head), recursion happens here:

ListNode last = reverseList(head.next);

Don’t get lost in recursion (your brain can only hold so many stacks!). Instead, use the function definition to understand what this code does:

After reverseList(head.next) finishes, the whole list becomes:

And according to the function definition, the reverseList function returns the new head of the reversed list, which we store in the variable last.

Now, look at the next line:

head.next.next = head;

Next:

head.next = null;
return last;

Amazing! Now the whole linked list is reversed. Recursive code is simple and elegant, but there are two things to pay attention to:

1. The recursive function needs a base case, which is this line:

if (head == null || head.next == null) {
    return head;
}

This means if the list is empty or only has one node, the reversed result is itself, so just return it.

1. After the list is reversed recursively, the new head is last, and the old head becomes the last node. Don't forget to set its next to null:

head.next = null;

This way, the whole linked list is reversed. Isn’t it amazing? Here is a visual process of recursive reversal:

::: note Do not get lost in recursion details

The visual panel can show all the steps of the recursion, but I do not suggest beginners focus too much on the details. First, use the way of thinking explained above to understand recursion, then use the visual panel to deepen your understanding.

:::

::: note Recursion is less efficient than iteration for linked lists

It is worth mentioning that recursion is not very efficient for linked lists.

The recursive and iterative solutions both have time complexity O(N), but the iterative one uses O(1) space, while the recursive one needs stack space, so its space complexity is O(N).

So, recursion is good for practicing thinking, but for efficiency, iteration is better.

:::

Reverse the First N Nodes of a Linked List

Now let’s implement a function like this:

// Reverse the first n nodes of the linked list (n <= length of the list)
ListNode reverseN(ListNode head, int n)

For example, for the linked list below, if you run reverseN(head, 3):

Iterative Solution

The iterative solution is easy to write. You can modify the reverseList function we wrote before:

ListNode reverseN(ListNode head, int n) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode pre, cur, nxt;
    pre = null; cur = head; nxt = head.next;
    while (n > 0) {
        cur.next = pre;
        pre = cur;
        cur = nxt;
        if (nxt != null) {
            nxt = nxt.next;
        }
        n--;
    }
    // At this point, cur is the (n+1)th node, and head is the tail node after reversal
    head.next = cur;
    /**<extend up>
    ![](../pictures/reverse-linked-list/6.jpg)
    */
    // At this point, pre is the head node after reversal
    return pre;
}

Recursive Solution

The recursive idea is similar to reversing the whole linked list. You just need a small change:

// Successor node
ListNode successor = null;

// Reverse n nodes starting from head, return the new head node
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // Record the (n+1)th node
        successor = head.next;
        return head;
    }
    // Starting from head.next, need to reverse the first n-1 nodes
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // Connect the reversed head node with the nodes after it
    head.next = successor;
    return last;
    /**<extend up -90>
    ![](../pictures/reverse-linked-list/7.jpg)
    */
}

Main differences:

1. The base case becomes n == 1. Reversing one element means it stays the same. You also need to record the successor node, which is the n + 1 node.

2. Before, we set head.next to null because after reversing the whole list, the original head becomes the last node. Now, after recursion, head may not be the last node. So you need to record the successor (n + 1 node) and connect head to it after reversing.

Reverse a Part of a Linked List

We can go further. Given a range of indices, reverse that part in the linked list and keep other parts unchanged.

LeetCode 92 "Reverse Linked List II" is this problem:

LeetCode 92. Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:**

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

Example 2:**

**Input:** head = [5], left = 1, right = 1
**Output:** [5]

Constraints:

• The number of nodes in the list is n.

• 1 <= n <= 500

• -500 <= Node.val <= 500

• 1 <= left <= right <= n

Follow up: Could you do it in one pass?

The function gets index range [m, n] (1-based). You only reverse the elements in this range. The function signature:

ListNode reverseBetween(ListNode head, int m, int n)

Iterative Solution

The iterative idea is simple. First, find the m - 1 node, then use the reverseN function we wrote before:

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == 1) {
            return reverseN(head, n);
        }
        // find the predecessor of the m-th node
        ListNode pre = head;
        for (int i = 1; i < m - 1; i++) {
            pre = pre.next;
        }
        // start reversing from the m-th node
        pre.next = reverseN(pre.next, n - m + 1);
        return head;
    }

    ListNode reverseN(ListNode head, int n) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre, cur, nxt;
        pre = null; cur = head; nxt = head.next;
        while (n > 0) {
            cur.next = pre;
            pre = cur;
            cur = nxt;
            if (nxt != null) {
                nxt = nxt.next;
            }
            n--;
        }
        // at this point, cur is the (n+1)-th node, head is the tail node after reversal
        head.next = cur;
        /**<extend up>
        ![](../pictures/reverse-linked-list/6.jpg)
        */
        // at this point, pre is the head node after reversal
        return pre;
    }
}

Recursive Solution

For the recursive solution, also find the m - 1 node and use the reverseN function.

The key is: how to find the m - 1 node with recursion?

If we treat head as index 1, we want to reverse from the mth node. If we treat head.next as index 1, then we should reverse from the m - 1th node. For head.next.next, it’s from the m - 2th node, and so on...

This is using recursion to move forward. The code can be written like this:

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // base case
        if (m == 1) {
            return reverseN(head, n);
        }
        // advance to the starting point of reversal to trigger the base case
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }

    // successor node
    ListNode successor = null;

    // reverse n nodes starting from head, return the new head node
    ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // record the (n+1)th node
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);

        head.next.next = head;
        head.next = successor;
        return last;
    }
}

Reverse Nodes in k-Group

This problem often appears in interviews, and its difficulty on LeetCode is Hard. Let's look at the question:

LeetCode 25. Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:**

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

Example 2:**

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

Constraints:

• The number of nodes in the list is n.

• 1 <= k <= n <= 5000

• 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

With the previous explanations, is this problem really that hard? Actually, if you use the idea of "breaking down the problem" and reuse the reverseN function from before, it becomes much easier.

Idea

If you think carefully, you will find that this problem has a recursive nature.

For example, let's call reverseKGroup(head, 2) on a linked list. This means we reverse the list in groups of 2:

If we manage to reverse the first 2 nodes, what about the rest of the nodes? The rest is also a linked list, but smaller in size. This is a smaller subproblem with the same structure.

We can move the head pointer to the start of the next part of the list, and then call reverseKGroup(head, 2) recursively:

Once we find the recursive structure, the general algorithm is clear:

1. First, reverse the first k nodes starting from head. Here, we can reuse the reverseN function we implemented before.

2. Use the (k+1)th node as head, and make a recursive call to reverseKGroup.

3. Connect the results from the above two steps.

Code

With the step-by-step explanation above, the code can be written directly. Here I use the iterative version of the reverseN function. You can also use the recursive one if you like:

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        // interval [a, b) contains k elements to be reversed
        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++) {
            // if there are less than k elements, no need to reverse
            if (b == null) return head;
            b = b.next;
        }
        // reverse the first k elements
        ListNode newHead = reverseN(a, k);
        // at this point, b points to the head node of the next group to be reversed
        // recursively reverse the subsequent linked list and connect them
        a.next = reverseKGroup(b, k);
        /**<extend up -90>
        ![](../pictures/kgroup/6.jpg)
        */
        return newHead;
    }

    // function to reverse the first N nodes implemented above
    ListNode reverseN(ListNode head, int n) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre, cur, nxt;
        pre = null; cur = head; nxt = head.next;
        while (n > 0) {
            cur.next = pre;
            pre = cur;
            cur = nxt;
            if (nxt != null) {
                nxt = nxt.next;
            }
            n--;
        }
        head.next = cur;
        /**<extend up>
        ![](../pictures/reverse-linked-list/6.jpg)
        */
        return pre;
    }
}

Very quickly, the problem is solved.

Summary

The idea of recursion is a bit harder to understand than iteration. The trick is: do not get lost in recursion, but use clear definitions to write your algorithm.

When you face a difficult problem, try to break it into smaller parts. Modify simple solutions to solve harder problems.