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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A heap is a ...?

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Example Walkthrough

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

11 -> 2 -> 3 -> null

We want to reverse it to become:

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

1dummy -> null
2curr -> 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.

1next -> 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.
1dummy -> null <- 1    2 -> 3 -> null
2curr ---------^      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.
1dummy -> 1 -> null
2         ^
3curr ----|
  1. We update curr to next, moving forward in the original list. curr now points to 2.
1dummy -> 1 -> null
2curr -> 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:
1dummy -> 2 -> 1 -> null
2         ^
3curr ----|    3 -> null
4         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:
1dummy -> 3 -> 2 -> 1 -> null
2         ^
3curr ----|

  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
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫