Reverse Linked List

Tags

Reverse Linked List

Category

Linked Lists

Difficulty

Medium

Problem Statement

Given the head of a singly linked list, reverse the list in place and return the new head (which was the original tail). Each node's next pointer should point to the previous node, and the original head's next should become null.

Intuition

To reverse a linked list, we need to make each node point to its predecessor instead of its successor. We can do this iteratively by maintaining three pointers: the previous node, the current node, and the next node. At each step, we redirect the current node's next pointer to the previous node, then shift all three pointers forward. When the current pointer reaches null, the previous pointer is at the new head.

Approach

  1. Initialize previous to null and current to head.
  2. While current is not null: a. Save current.next in a temporary variable next. b. Set current.next = previous (reverse the link). c. Move previous = current. d. Move current = next.
  3. Return previous (the new head of the reversed list).

Pseudocode

function reverseLinkedList(head):
    previous = null
    current = head

    while current is not null:
        next = current.next
        current.next = previous
        previous = current
        current = next

    return previous

Time & Space Complexity

  • Time: O(n), where n is the number of nodes. Each node is visited exactly once.
  • Space: O(1). Only three pointers are used regardless of list size.

Key Insights

  • The iterative three-pointer approach is the most straightforward and space-efficient method.
  • A recursive solution also works: reverse the rest of the list, then fix the pointers. However, it uses O(n) stack space.
  • After reversal, the original head becomes the tail with next = null.
  • This is a fundamental building block used in many other linked list problems (e.g., reverse in groups, palindrome check).

Edge Cases

  • Empty list (head is null): return null.
  • Single node: return the same node (no links to reverse).
  • Two nodes: a simple swap of the link direction.
  • Already "reversed" (the algorithm does not care about values, only structure).

Linked mentions