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

Middle Of The Linked List Problem

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

Linked List Components Problem

LeetCode 817. You are given the head of a linked...

Split Linked List In Parts Problem

LeetCode 725. Given the head of a singly linked list...

All O'One Data Structure Problem

LeetCode 432. Design a data structure to store the strings...

Add Two Numbers II Problem

LeetCode 445. You are given two non-empty linked lists representing...