Tricks to Reverse a Linked List Recursively

Reversing a singly linked list using an iterative approach is not difficult, but the recursive implementation can be a bit challenging. If we add another layer of complexity by asking you to reverse only a part of the singly linked list, can you achieve this using both iterative and recursive methods? Furthermore, if you were asked to reverse the list in groups of k nodes, how would you handle it?

This article will delve from the basics to the advanced, tackling these linked list manipulation problems all at once. I will use both recursive and iterative approaches, and combine them with visual aids to help you understand, thereby strengthening your recursive thinking and your ability to manipulate linked list pointers.

Reversing the Entire Singly Linked List

In platforms like LeetCode, the general structure of a singly linked list is as follows:

// Structure of a single linked list node
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// Structure of a single linked list node
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

# Structure of a singly linked list node
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

// Structure of a singly linked list node
type ListNode struct {
    val  int
    next *ListNode
}

// Structure of a singly linked list node
var ListNode = function(x) {
    this.val = x;
    this.next = null;
}

Reversing a singly linked list is a basic algorithm problem. LeetCode's problem #206, "Reverse Linked List," addresses this issue:

206. Reverse Linked List | LeetCode |

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?

Let's try solving this problem using multiple methods.

Iterative Solution

The standard approach to this problem is the iterative method. It involves manipulating several pointers to reverse the direction of each node in the list. There are no major difficulties, just details related to pointer operations.

Here is the code directly. With the help of comments and the visualization 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
        // cur is the current node being traversed, pre is the
        // predecessor node of cur, nxt is the successor node
        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;
    }
}

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

class Solution:
    # Reverse the linked list starting from head
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        # Due to the structure of a singly linked list, at least
        # three pointers are needed to complete the iterative
        # cur is the current node being traversed, pre is the
        # predecessor node of cur, nxt is the successor node
        pre, cur, nxt = None, head, head.next
        while cur is not None:
            # Reverse each node
            cur.next = pre
            # Update pointer positions
            pre = cur
            cur = nxt
            if nxt is not None:
                nxt = nxt.next
        # Return the head node after reversal
        return pre

// Reverse a singly linked list starting from head

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // Due to the structure of a singly linked list, at least
    // three pointers are needed to complete the iterative
    // cur is the current node being traversed, pre is the
    // predecessor node of cur, and nxt is the successor node
    var pre, cur, nxt *ListNode
    pre, cur, nxt = nil, head, head.Next
    for cur != nil {
        // Reverse each node
        cur.Next = pre
        // Update pointer positions
        pre = cur
        cur = nxt
        if nxt != nil {
            nxt = nxt.Next
        }
    }
    // Return the head node of the reversed list
    return pre
}

var reverseList = function(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
    // cur is the current node being traversed, pre is the
    // predecessor node of cur, and nxt is the successor node
    var 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;
}

Recursive Solution

While the iterative solution above involves some cumbersome pointer manipulation, the logic is relatively clear. How would you feel about using recursion to reverse a singly linked list?

It might be challenging for beginners to come up with this idea, and that's normal. If you study the binary tree series algorithms discussed later, you might be able to figure out this algorithm when you revisit this problem.

Since the binary tree structure is an extension of the singly linked list, essentially a binary linked list, the recursive thinking applied to binary trees can be similarly applied to singly linked lists.

The key to recursively reversing a singly linked list lies in the fact that the problem itself has a subproblem structure.

For example, if you are given a singly linked list starting with node 1 as 1->2->3->4, and you ignore the head node 1, taking only the sub-list 2->3->4, it is still a singly linked list, right?

Your reverseList function can reverse any singly linked list you input, correct? So, can you use this function to first reverse the sub-list 2->3->4, and then find a way to attach 1 to the end of the reversed list 4->3->2? Wouldn't that complete the reversal of the entire list?

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

This is the idea of "problem decomposition." By defining a recursive function, we break down the original problem into several smaller subproblems with the same structure. Finally, we assemble the solution to the original problem from the solutions to these subproblems.

There will be a dedicated chapter in the following tutorials to explain and practice this way of thinking, so we won't elaborate on it here.

Let's first look at the code implementation 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
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverseList(head.next);

        head.next.next = head;

        head.next = null;

        return last;
    }
}

class Solution {
public:
    // Definition: Input a head node of a singly linked
    // list, reverse the list, and return the new head
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* last = reverseList(head->next);

        head->next->next = head;

        head->next = nullptr;

        return last;
    }
};

class Solution:
    # Definition: Input a head node of a singly linked
    # list, reverse the list, and return the new head
    def reverseList(self, head):
        if head is None or head.next is None:
            return head
        last = self.reverseList(head.next) 

        head.next.next = head 

        head.next = None

        return last

// Definition: Input the head node of a singly linked
// list, reverse the list, and return the new head node
func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	last := reverseList(head.Next)

	head.Next.Next = head

	head.Next = nil

	return last
}

var reverseList = function(head) {
    // Definition: Input a head node of a singly linked
    // list, reverse the list, and return the new head
    if (head == null || head.next == null) {
        return head;
    }
    var last = reverseList(head.next);

    head.next.next = head;

    head.next = null;

    return last;
}

This algorithm is often used to demonstrate the elegance and ingenuity of recursion. Let's explain this code in detail, and finally, provide a visualization panel for you to explore the recursion process on your own.

For recursive algorithms that follow the "problem decomposition" approach, the most crucial part is clearly defining the recursive function. Specifically, the definition of our reverseList function is as follows:

Given a node head, the function reverses the linked list starting from head and returns the new head node after reversal.

With the function definition understood, let's look at the problem. For example, if we want to reverse this linked list:

Upon inputting reverseList(head), the recursion will proceed as follows:

ListNode last = reverseList(head.next);

Do not dive into recursion immediately (how many stacks can your brain manage, anyway?). Instead, use the function definition to understand what result this piece of code will produce:

After executing reverseList(head.next), the entire linked list transforms as follows:

According to the function definition, the reverseList function returns the head node of the reversed list, which we store in the variable last.

Now, let's examine the following code:

head.next.next = head;

Next:

head.next = null;
return last;

Isn't it amazing how the entire linked list is reversed like that? Recursive code is this concise and elegant, but there are two points to note:

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

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

This means that if the linked list is empty or contains only one node, the reversed result is itself, so you can return it directly.

2. After the linked list is recursively reversed, the new head node is last, and the previous head becomes the last node. Don't forget the end of the linked list should point to null:

head.next = null;

In this way, the entire singly linked list is reversed. Isn't it amazing? Below is the visualization of the recursive reversal process of the linked list:

Reverse the First N Nodes of a Linked List

This time, we will 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)

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

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

// Reverse the first n nodes of the linked list (n <= length of the list)
func ReverseN(head *ListNode, n int) *ListNode {}

// Reverse the first n nodes of the linked list (n <= length of the linked list)
var reverseN = function(head, n) {}

For example, for the linked list shown below, executing reverseN(head, 3):