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




Related Posts

Intersection Of Two Linked Lists Problem

LeetCode 160. Given the heads of two singly linked-lists headA...

Sort List Problem

LeetCode 148. Given the head of a linked list, return...

Reorder List Problem

LeetCode 143. You are given the head of a singly...

Linked List Cycle Problem

LeetCode 141. Given head, the head of a linked list,...

Linked List Cycle II Problem

LeetCode 142. Given the head of a linked list, return...

Insertion Sort List Problem

LeetCode 147. Given the head of a singly linked list,...