206. Reverse Linked List

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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:

A new ListNode called dummy is created, which acts as the placeholder before the new reversed list's head.
A pointer called curr is initialized to point to the head of the original list. This pointer is used to iterate over the list.
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.
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.
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.
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.
curr is updated to next to move to the next node in the original list, using the pointer we saved earlier.
Once all nodes have been processed and the loop exits, dummy.next will be the head of the new reversed list.
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:

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.
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

Starting the iteration, we enter the while loop since curr is not null.
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

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 ----^

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

We update curr to next, moving forward in the original list. curr now points to 2.

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

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 --^

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

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.
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:

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don't know