206. Reverse Linked List

EasyRecursionLinked List
Leetcode Link

Problem Description

The task is to reverse a singly linked list. A linked list is a data structure where each element (often called a 'node') contains a value and a pointer/reference to the next node in the sequence. A singly linked list means that each node points to the next node and there is no reference to previous nodes. The problem provides a pointer to the head of the linked list, where the 'head' represents the first node in the list. Our goal is to take this linked list and return it in the reversed order. For instance, if the linked list is 1 -> 2 -> 3 -> null, the reversed list should be 3 -> 2 -> 1 -> null.

Intuition

To reverse the linked list, we iterate over the original list and rearrange the next pointers without creating a new list. The intuition behind this solution is to take each node and move it to the beginning of the new reversed list as we traverse through the original list. We maintain a temporary node, often referred to as a 'dummy' node, which initially points to null, as it will eventually become the tail of the reversed list once all nodes are reversed.

We iterate from the head towards the end of the list, and with each iteration, we do the following:

  • Temporarily store the next node (since we are going to disrupt the next reference of the current node).
  • Set the next reference of the current node to point to what is currently the first node of the reversed list (initially, this is null or dummy.next).
  • Move the dummy's next reference to the current node, effectively placing the current node at the beginning of the reversed list.
  • Move to the next node in the original list using the reference we stored earlier.

This process ensures that we do not lose track of the remaining parts of the original list while building the reversed list. After we have iterated through the entire original list, the dummy.next will point to the new head of the reversed list, which we then return as the result.

Learn more about Recursion and Linked List patterns.

Solution Approach

The provided solution employs an iterative approach to go through each node in the linked list and reverse the links. Here's a step-by-step walk-through of the algorithm used:

  1. A new ListNode called dummy is created, which acts as the placeholder before the new reversed list's head.

  2. A pointer called curr is initialized to point to the head of the original list. This pointer is used to iterate over the list.

  3. The iteration starts with a while loop which continues as long as curr is not null. This ensures we process all nodes in the list.

  4. Inside the loop, next temporarily stores curr.next, which is the pointer to the next node in the original list. This is crucial since we are going to change curr.next to point to the new list and we don't want to lose the reference to the rest of the original list.

  5. We then set curr.next to point to dummy.next. Since dummy.next represents the start of the new list, or null in the first iteration, the current node now points to the head of the reversed list.

  6. dummy.next is updated to curr to move the starting point of the reversed list to the current node. At this point, curr is effectively inserted at the beginning of the new reversed list.

  7. curr is updated to next to move to the next node in the original list, using the pointer we saved earlier.

  8. Once all nodes have been processed and the loop exits, dummy.next will be the head of the new reversed list.

  9. The new reversed list referenced by dummy.next is returned.

By updating the next pointers of each node, the solution reverses the direction of the list without allocating any additional nodes, which makes it an in-place reversal with a space complexity of O(1). Each node is visited once, resulting in a time complexity of O(n), where n is the number of nodes in the list.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following linked list:

1 -> 2 -> 3 -> null

We want to reverse it to become:

3 -> 2 -> 1 -> null

Here's the step-by-step process to achieve that using the provided algorithm:

  1. We create a ListNode called dummy that will initially serve as a placeholder for the reversed list. At the beginning, dummy.next is set to null.

  2. We initialize a pointer curr to point to the head of the original list which is the node with the value 1.

dummy -> null
curr -> 1 -> 2 -> 3 -> null

  1. Starting the iteration, we enter the while loop since curr is not null.

  2. We store curr.next in next, so next points to 2. next will help us move forward in the list after we've altered curr.next.

next -> 2 -> 3 -> null
  1. We update curr.next to point to dummy.next, which is currently null. Now the first node (1) points to null, the start of our new reversed list.
dummy -> null <- 1    2 -> 3 -> null
curr ---------^      next ----^
  1. We move the start of the reversed list to curr by setting dummy.next to curr. The reversed list now starts with 1.
dummy -> 1 -> null
         ^
curr ----|
  1. We update curr to next, moving forward in the original list. curr now points to 2.
dummy -> 1 -> null
curr -> 2 -> 3 -> null
  1. The loop continues. Again, we save curr.next to next, and update curr.next to point to dummy.next. Then we shift the start of the reversed list by setting dummy.next to the current node and update curr to next. After this iteration, dummy points to the new head 2, and our reversed list grows:
dummy -> 2 -> 1 -> null
         ^
curr ----|    3 -> null
         next --^
  1. In the final iteration, we perform similar steps. We save curr.next to next, set curr.next to dummy.next, and move dummy.next to curr. curr is then updated to the null we saved in next:
dummy -> 3 -> 2 -> 1 -> null
         ^
curr ----|

  1. Once curr is null, the while loop terminates, and we find that dummy.next points to 3, which is the new head of the reversed list.

  2. Lastly, we return the reversed list starting from dummy.next, which is 3 -> 2 -> 1 -> null.

And that completes the reversal of our linked list using the iterative approach described in the solution.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7class Solution:
8    def reverseList(self, head: ListNode) -> ListNode:
9        # Initialize a dummy node, which will be the new head after reversal
10        dummy_node = ListNode()
11      
12        # Start from the head of the list
13        current_node = head
14      
15        # Iterate over the linked list
16        while current_node is not None:
17            # Save the next node
18            next_node = current_node.next
19          
20            # Reverse the link so that current_node.next points to the node before it
21            current_node.next = dummy_node.next
22            dummy_node.next = current_node
23          
24            # Move to the next node in the original list
25            current_node = next_node
26      
27        # The dummy node's next now points to the head of the reversed list
28        return dummy_node.next
29
1// Definition for singly-linked list.
2class ListNode {
3    int val;
4    ListNode next;
5    ListNode() {}
6    ListNode(int val) { this.val = val; }
7    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
8}
9
10class Solution {
11
12    /**
13     * Reverses the given linked list.
14     *
15     * @param head The head of the original singly-linked list.
16     * @return The head of the reversed singly-linked list.
17     */
18    public ListNode reverseList(ListNode head) {
19        // Dummy node that will help in reversing the list.
20        ListNode dummy = new ListNode();
21      
22        // Pointer to traverse the original list.
23        ListNode current = head;
24      
25        // Iterating through each node in the list.
26        while (current != null) {
27            // Temporary store the next node.
28            ListNode nextTemp = current.next;
29
30            // Reversing the link so that current.next points to the new head (dummy.next).
31            current.next = dummy.next;
32
33            // Move the dummy's next to the current node making it the new head of the reversed list.
34            dummy.next = current;
35
36            // Move to the next node in the original list.
37            current = nextTemp;
38        }
39      
40        // Return the reversed linked list which is pointed by dummy's next.
41        return dummy.next;
42    }
43}
44
1// Definition for singly-linked list node.
2struct ListNode {
3    int val;            // The value of the node.
4    ListNode *next;     // Pointer to the next node in the list.
5
6    // Default constructor initializes with default values.
7    ListNode() : val(0), next(nullptr) {}
8
9    // Constructor initializes with a given value and next pointer set to nullptr.
10    ListNode(int x) : val(x), next(nullptr) {}
11
12    // Constructor initializes with a given value and a given next node pointer.
13    ListNode(int x, ListNode *next) : val(x), next(next) {}
14};
15
16class Solution {
17public:
18    // Function to reverse a singly-linked list.
19    ListNode* reverseList(ListNode* head) {
20        // The 'dummy' node acts as the new head of the reversed list.
21        ListNode* dummy = new ListNode();
22
23        // 'current' node will traverse the original list.
24        ListNode* current = head;
25
26        // Iterate through the list until we reach the end.
27        while (current != nullptr) {
28            // 'nextNode' temporarily stores the next node.
29            ListNode* nextNode = current->next;
30
31            // Reverse the 'current' node's pointer to point to the new list.
32            current->next = dummy->next;
33
34            // The 'current' node is prepended to the new list.
35            dummy->next = current;
36
37            // Move to the next node in the original list.
38            current = nextNode;
39        }
40
41        // The head of the new reversed list is 'dummy->next.'
42        return dummy->next;
43    }
44};
45
1// Definition for a node in a singly-linked list
2interface ListNode {
3    val: number;
4    next: ListNode | null;
5}
6
7/**
8 * Reverses a singly linked list.
9 * @param {ListNode | null} head - The head node of the linked list to be reversed
10 * @return {ListNode | null} The new head of the reversed linked list
11 */
12function reverseList(head: ListNode | null): ListNode | null {
13    // Return immediately if the list is empty
14    if (head === null) {
15        return head;
16    }
17
18    // Initialize pointers
19    let previousNode: ListNode | null = null; // Previous node in the list
20    let currentNode: ListNode | null = head;  // Current node in the list
21
22    // Iterate through the list
23    while (currentNode !== null) {
24        const nextNode: ListNode | null = currentNode.next; // Next node in the list
25
26        // Reverse the current node's pointer
27        currentNode.next = previousNode;
28
29        // Move the previous and current pointers one step forward
30        previousNode = currentNode;
31        currentNode = nextNode;
32    }
33
34    // By the end, previousNode is the new head of the reversed linked list
35    return previousNode;
36}
37

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the number of nodes in the linked list. This is because the code iterates through all the nodes in the list a single time.

The space complexity of the code is O(1). The space used does not depend on the size of the input list, since only a finite number of pointers (dummy, curr, next) are used, which occupy constant space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which type of traversal does breadth first search do?

Recommended Readings

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Want a Structured Path to Master System Design Too? Don’t Miss This!

Praneeth Rudroji

Intuition

To reverse a linked list, the goal is to modify the pointers between nodes so that each node points to its predecessor instead of its successor. A useful way to visualize this is to consider creating a new linked list where each node is added at the head. This can help us conceptualize how to traverse the original list and insert nodes in reverse order.

In our approach:

  • We will identify the last node of the original linked list to facilitate inserting new nodes.
  • We will also track the number of nodes in the list to help with the reversal process.

Approach

  1. Identify the Last Node and Count Nodes:

    • Traverse the linked list to find the last node and simultaneously count the number of nodes in the list.

  2. Iterate Through the List:

    • Using a temporary pointer, iterate through the original list.
    • For each node, adjust the pointers to insert the node at the beginning of the new reversed list.

  3. Reassign Pointers:

    • Each time you take a node from the original list, make its next point to the current head of the reversed list (which starts as null).
    • Update the head of the reversed list to be the newly added node.

  4. Return the New Head:

    • Once all nodes have been processed, return the new head of the reversed list.

Code Implementation

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode lastNode = head;
        int count = 0;
        
        // Step 1: Find the last node and count nodes
        while (lastNode != null && lastNode.next != null) {
            lastNode = lastNode.next;
            count++;
        }
        
        ListNode temp = head;
        
        // Step 2: Reverse the list
        while (count != 0) {
            ListNode firstNode = temp;
            temp = firstNode.next; // Move temp to the next node
            firstNode.next = lastNode.next; // Insert at the head of the reversed list
            lastNode.next = firstNode; // Update lastNode to point to firstNode
            count--;
        }

        // Step 3: Return the new head
        return lastNode; // lastNode is now the head of the reversed list
    }
}
Sun Nov 03 2024