Skip to content

Reverse Linked List

Understanding the Reverse Linked List Problem

Reversing a linked list is a common problem in data structures and algorithms. This problem not only tests your understanding of linked lists but also your ability to implement recursive and iterative solutions. In this article, we will delve deep into the Reverse Linked List problem, specifically focusing on the Leetcode problem 206. We will explore both recursive and iterative approaches, providing code examples and analyzing their complexities.

Problem Overview

The objective of the Reverse Linked List problem is straightforward: given the head of a singly linked list, we need to reverse the list and return the new head of the reversed list. For example, if the linked list is represented as 1 -> 2 -> 3 -> 4 -> 5, after reversing, it should become 5 -> 4 -> 3 -> 2 -> 1.

To achieve this, we will discuss two primary approaches: the recursive method and the iterative method. Each approach has its own advantages and nuances, which we will explore in detail.

Recursive Approach

The recursive approach to reversing a linked list is elegant and intuitive. It involves breaking down the problem into smaller subproblems until we reach a base case. Let’s outline the steps involved in this approach.

Understanding the Recursive Process

We start with the head of the linked list. The recursion will continue until we reach the last node. The last node will become the new head of the reversed list. Here’s how it works:

  1. Identify the base case: If the head is null or if there is only one node, return the head.
  2. Recursively call the function on the next node (head.next).
  3. After returning from recursion, reverse the link by setting head.next.next to head.
  4. Set head.next to null to prevent cycles.
  5. Return the new head.

Visualizing the Process

Consider a linked list of five nodes: 1 -> 2 -> 3 -> 4 -> 5. Here’s a breakdown of the recursive calls:

  • Call reverse on node 1.
  • Call reverse on node 2.
  • Call reverse on node 3.
  • Call reverse on node 4.
  • Call reverse on node 5 (base case reached).

As we return from the recursion, we reverse the links:

  • 5’s next points to 4.
  • 4’s next points to 3.
  • 3’s next points to 2.
  • 2’s next points to 1.

Java Code Implementation

Here’s how you can implement the recursive approach in Java:

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head; // Base case
    }
    ListNode newHead = reverseList(head.next); // Recursive call
    head.next.next = head; // Reverse the link
    head.next = null; // Prevent cycle
    return newHead; // Return the new head
}

Complexity Analysis

The time complexity of the recursive approach is O(n), where n is the number of nodes in the linked list. This is because we are visiting each node once. The space complexity is also O(n) due to the recursion stack.

Iterative Approach

While the recursive approach is elegant, it may not always be the most efficient in terms of space. The iterative approach provides a more space-efficient solution, using only a constant amount of space.

Understanding the Iterative Process

In the iterative approach, we use three pointers: previous, current, and next. The goal is to traverse the list and reverse the links as we go. Here’s how it works:

  1. Initialize the previous pointer to null and the current pointer to the head.
  2. While current is not null:
    • Store the next node (current.next).
    • Reverse the current node’s link (current.next = previous).
    • Move previous to current and current to next.
  3. Return previous as the new head.

Visualizing the Iterative Process

For the same linked list 1 -> 2 -> 3 -> 4 -> 5, the iterative process works as follows:

  • Start with previous = null and current = 1.
  • Reverse the link of node 1 to null.
  • Move previous to node 1 and current to node 2.
  • Continue this process until current becomes null.

Java Code Implementation

Here’s the Java implementation for the iterative approach:

public ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextTemp = current.next; // Store next node
        current.next = previous; // Reverse link
        previous = current; // Move previous forward
        current = nextTemp; // Move current forward
    }
    return previous; // Return new head
}

Complexity Analysis

The time complexity of the iterative approach is also O(n), as we visit each node once. However, the space complexity is O(1) since we are using a fixed amount of space regardless of the input size.

Conclusion

In summary, the Reverse Linked List problem is a classic exercise in understanding linked lists. Both the recursive and iterative approaches have their merits. The recursive method is succinct and elegant, while the iterative method is more space-efficient. Depending on the context and constraints, you can choose the approach that best fits your needs.

Practice implementing both methods to strengthen your understanding. As you work through more complex problems, these foundational concepts will serve you well. Happy coding!

Algorithms made easy