## 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* prevNode;
ListNode* nextNode;
ListNode* currNode;

while (currNode != NULL) {
nextNode = currNode->next;
currNode->next = prevNode;
prevNode = currNode;
currNode = nextNode;
}

return prevNode;
}

int main() {
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);

cout << head->val << " ";
}
return 0;
}
``````