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
.
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 isnull
ordummy.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
calleddummy
is created, which acts as the placeholder before the new reversed list's head. -
A pointer called
curr
is initialized to point to thehead
of the original list. This pointer is used to iterate over the list. -
The iteration starts with a
while
loop which continues as long ascurr
is notnull
. This ensures we process all nodes in the list. -
Inside the loop,
next
temporarily storescurr.next
, which is the pointer to the next node in the original list. This is crucial since we are going to changecurr.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 todummy.next
. Sincedummy.next
represents the start of the new list, ornull
in the first iteration, the current node now points to the head of the reversed list. -
dummy.next
is updated tocurr
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 tonext
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 EvaluatorExample 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
calleddummy
that will initially serve as a placeholder for the reversed list. At the beginning,dummy.next
is set tonull
. -
We initialize a pointer
curr
to point to the head of the original list which is the node with the value1
.
dummy -> null curr -> 1 -> 2 -> 3 -> null
-
Starting the iteration, we enter the
while
loop sincecurr
is notnull
. -
We store
curr.next
innext
, sonext
points to2
.next
will help us move forward in the list after we've alteredcurr.next
.
next -> 2 -> 3 -> null
- We update
curr.next
to point todummy.next
, which is currentlynull
. Now the first node (1
) points tonull
, 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 settingdummy.next
tocurr
. The reversed list now starts with1
.
dummy -> 1 -> null ^ curr ----|
- We update
curr
tonext
, moving forward in the original list.curr
now points to2
.
dummy -> 1 -> null curr -> 2 -> 3 -> null
- The loop continues. Again, we save
curr.next
tonext
, and updatecurr.next
to point todummy.next
. Then we shift the start of the reversed list by settingdummy.next
to the current node and updatecurr
tonext
. After this iteration,dummy
points to the new head2
, 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
tonext
, setcurr.next
todummy.next
, and movedummy.next
tocurr
.curr
is then updated to thenull
we saved innext
:
dummy -> 3 -> 2 -> 1 -> null ^ curr ----|
-
Once
curr
isnull
, thewhile
loop terminates, and we find thatdummy.next
points to3
, which is the new head of the reversed list. -
Lastly, we return the reversed list starting from
dummy.next
, which is3 -> 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.
A heap is a ...?
Recommended Readings
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 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 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!