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 fundamental algorithm problem, exemplified by LeetCode problem 206, "Reverse Linked List":

Let's explore multiple methods to solve this problem.

Iterative Solution

The conventional approach to this problem is the iterative solution. It involves manipulating a few pointers to reverse the direction of pointers for each node in the list. The difficulty lies primarily in the details of pointer operations.

Here is the code; it should be easy to understand with the comments and visual aids:

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

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 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 = 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 reversal
        # cur is the current node being traversed, pre is the
        # predecessor node of cur, nxt is the successor node of cur
        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 reversal
    // cur is the current node being traversed, pre is the
    // predecessor node of cur, and nxt is the successor node of cur
    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 reversal
    // cur is the current node being traversed, pre is the
    // predecessor node of cur, and nxt is the successor node of cur
    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

The iterative approach to manipulating pointers above may be a bit tedious, but the thought process is relatively clear. Now, if you were asked to reverse a singly linked list using recursion, what would you think?

For beginners, it might be hard to come up with this idea, which is normal. If you learn about binary tree algorithms and their reasoning in later sections, you'll have a better chance of figuring out this algorithm on your own when you revisit this problem.

This is because the binary tree structure is essentially an extension of a singly linked list, like a binary linked list. Therefore, the recursive thinking used in binary trees can be applied to singly linked lists as well.

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

For instance, if you're given a singly linked list 1->2->3->4 with 1 as the head node, and you ignore this head node 1, focusing only on the sublist 2->3->4, it is still a singly linked list, right?

So, your reverseList function should be able to reverse any singly linked list it receives. Can you use this function to first reverse the sublist 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 node
    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 node
    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 node
    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 node
    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):

Iterative Solution

Recursive Solution

Reverse a Portion of the Linked List

Iterative Solution

Recursive Solution

Reverse Nodes in K-Group

Thought Analysis

Code Implementation

Final Summary