Reverse a LinkedList

Dec 18, 2024 • 5 mins read
Hero Image

Problem Overview

The goal of this problem is to reverse a singly linked list. A linked list is a linear data structure that consists of nodes, where each node contains a value and a reference (or link) to the next node in the sequence. In this problem, you will receive the head of a singly linked list and you need to reverse the order of its nodes, such that the last node becomes the head, the second to last node comes after the new head, and so on.

Understanding the Problem

Given the head of a singly linked list, our task is to reverse the list and return the new head. For example, if the input linked list is 1 -> 2 -> 3 -> 4 -> 5, the reversed list should be 5 -> 4 -> 3 -> 2 -> 1. Understanding the traversal mechanics of the linked list is crucial to reversing it without losing its structure.

Key DSA concepts and theory

Linked List

A linked list is a common data structure used to store a collection of elements. Each element (node) holds a value and a pointer/reference to the next node in the sequence. There are different types of linked lists:

  • Singly Linked List: Each node has a single pointer to the next node.
  • Doubly Linked List: Each node has pointers to both previous and next nodes.
  • Circular Linked List: Last node points back to the first node.

Reversal Concept

Reversing a linked list involves changing the direction of the pointers. Each node's next pointer should point to its previous node. This requires careful handling of pointers to avoid losing access to the list nodes during the reversal process.

Solution Approach

Let's tackle the reversal with an iterative and a recursive approach.

Iterative Approach

The iterative method uses a trio of pointers to reverse the linked list: previous, current, and next.

Steps:

  1. Initialize previous as NULL and current as the head.
  2. Loop through the list:
    • Save the next node (current->next) in next.
    • Reverse the link by pointing current->next to previous.
    • Move previous and current one step forward (i.e., previous = current and current = next).
  3. When current is NULL, previous will be the new head of the reversed list.

C++ Code:

ListNode* reverseList(ListNode* head) {
    ListNode* previous = nullptr;
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* next = current->next; // Save next
        current->next = previous; // Reverse
        previous = current; // Advance previous
        current = next; // Advance current
    }
    return previous;
}

Java Code:

public ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

Recursive Approach

The recursive method works by solving the problem in a smaller sub-list repeatedly.

Steps:

  1. Base case: If the list is empty or contains only one node, return the list itself.
  2. Recursively reverse the rest of the list starting from the second node.
  3. Make the first node point to itself in reverse by adjusting the next pointers.
  4. Initially, set head->next->next = head and head->next = NULL.

C++ Code:

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode* reversedListHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return reversedListHead;
}

Java Code:

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode reversedListHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return reversedListHead;
}

Time and Space Complexity Analysis

Iterative Approach

  • Time Complexity: O(n), where n is the number of nodes in the linked list. We process each node exactly once.
  • Space Complexity: O(1), because we use a constant amount of extra space.

Recursive Approach

  • Time Complexity: O(n), similar to the iterative approach.
  • Space Complexity: O(n), due to the recursion stack, which will have n function calls for n nodes.

Common Mistakes to Avoid

  1. Losing Track of Nodes: Always ensure that you keep track of the next node before changing pointers.
  2. Null Checks: Always check if the list is empty to prevent accessing null pointers.
  3. Recursive Base Case: Ensure the base case is properly defined to prevent infinite recursion.

Similar Problems on LeetCode

  1. Reverse Linked List II (Question 92)
  2. Swap Nodes in Pairs (Question 24)
  3. Palindrome Linked List (Question 234)

Additional Resources and References

Mastering the art of reversing linked lists is a foundational skill that will prepare you for more complex data manipulation tasks in programming. Both iterative and recursive methods have their own usages, strengths, and weaknesses, and knowing both can provide flexibility in solving related challenges.