Reverse Linked List Problem
Description
LeetCode Problem 206. Reverse a singly linked list.
Example:
1
2
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Solution
To reverse the linked list, we need to modify the next pointer in each node to point to the previous node in the list. Let us consider an example:
1
1 -> 2 -> 3 -> NULL
If we would like to reverse this list, we need to point node 2 to node 1, and then point node 3 to node 2. To do that, we first use a pointer nextNode to record the next node of node 2 (currNode), which is node 3. And we use a pointer prevNode to point to the previous node of node 2, which is node 1.
1
2
prevNode currNode nextNode
1 -> 2 -> 3 -> NULL
Then we point currNode’s next pointer to the prevNode.
1
2
prevNode currNode nextNode
1 <- 2 -> 3 -> NULL
Then we move all three pointers to handle node 3.
1
2
prevNode currNode nextNode
1 <- 2 -> 3 -> NULL
Again, we point currNode’s next pointer to the prevNode.
1
2
prevNode currNode nextNode
1 <- 2 <- 3 -> NULL
Then we move all three pointers again, and repeat the above steps until currNode is NULL. This means we reach the end of the list.
1
2
prevNode currNode nextNode
1 <- 2 <- 3 -> NULL
Now we finish reversing the linked list. We can return prevNode, which is the head node of the reversed list.
The time complexity of the approach is O(n), and the space complexity is O(1).
Sample C++ Code
This is a C++ implementation of the above approach.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prevNode;
ListNode* nextNode;
ListNode* currNode;
if ((head == NULL) || (head->next == NULL))
return head;
currNode = head->next;
prevNode = head;
head->next = NULL;
while (currNode != NULL) {
nextNode = currNode->next;
currNode->next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
return prevNode;
}
int main() {
ListNode* lhead = new ListNode(1);
ListNode* curr = lhead;
curr->next = new ListNode(2);
curr = curr->next;
curr->next = new ListNode(3);
curr = curr->next;
curr->next = new ListNode(4);
curr = curr->next;
curr->next = new ListNode(5);
ListNode* head = reverseList(lhead);
while (head != nullptr) {
cout << head->val << " ";
head = head->next;
}
return 0;
}