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

Reverse Linked List Problem

LeetCode 206. Reverse a singly linked list.

Reverse Linked List II Problem

LeetCode 92. Reverse a linked list from position m to...

Palindrome Linked List Problem

LeetCode 234. Given a singly linked list, determine if it’s...

Merge K Sorted Lists Problem

LeetCode 23. You are given an array of k linked-lists...

Merge Two Sorted Lists Problem

LeetCode 21. Merge two sorted linked lists and return a...