Reverse Linked List

Explanation

1
* Step 0: ListNode* prev = NULL;
2
* ListNode* next = NULL;
3
* ListNode* curr = head;
4
*
5
* curr head
6
* v v
7
* NULL "1" -> "2" -> "3" -> NULL
8
* prev^ ^next
9
*
10
*
11
* Step 1: next = curr->next;
12
*
13
* curr head
14
* v v
15
* NULL "1" -> "2" -> "3" -> NULL
16
* prev^ ^next
17
*
18
*
19
* Step 2: curr->next = prev;
20
*
21
* curr head
22
* v v
23
* NULL <-- "1" "2" -> "3" -> NULL
24
* prev^ ^next
25
*
26
*
27
* Step 3: prev = curr;
28
* curr = next;
29
*
30
* head curr
31
* v v
32
* NULL <-- "1" "2" -> "3" -> NULL
33
* prev^ ^next
Copied!

C version

1
#include <stdio.h>
2
#include <stdlib.h>
3
4
struct Node{
5
struct Node* next;
6
int val;
7
};
8
9
10
void reverse(struct Node **head){
11
struct Node* prev = NULL;
12
struct Node* next = NULL;
13
struct Node* now = *head;
14
15
16
while(now != NULL){
17
next = now->next;
18
now->next = prev;
19
prev = now;
20
now = next;
21
}
22
*head = prev;
23
}
24
25
26
void enqueue(struct Node **root, int value){
27
struct Node* new_node = (struct Node*) malloc (sizeof(struct Node));
28
new_node->val = value;
29
new_node->next = *root;
30
*root = new_node;
31
32
}
33
34
void traverse(struct Node* ref){
35
struct Node* tmp = ref;
36
while(tmp!= NULL){
37
printf("%d\n", tmp->val);
38
tmp = tmp->next;
39
}
40
}
Copied!
Test code:
1
int main() {
2
3
struct Node* root = NULL;
4
5
enqueue(&root, 0);
6
enqueue(&root, 1);
7
enqueue(&root, 2);
8
enqueue(&root, 3);
9
enqueue(&root, 4);
10
11
traverse(root);
12
reverse(&root);
13
traverse(root);
14
return 0;
15
16
}
Copied!

Version 2: with single pointer head

1
void reverse(struct Node *head){
2
struct Node* prev = NULL;
3
struct Node* next = NULL;
4
struct Node* now = head;
5
6
7
while(now != NULL){
8
next = now->next;
9
now->next = prev;
10
prev = now;
11
now = next;
12
}
13
head = prev;
14
}
Copied!