Reverse Linked List

Search…
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!
Templates and methods - Previous
Trees with C/C++
Next - DS with C
Implement Queue with LL
Last modified 5mo ago
Copy link
Contents
Explanation
C version
Version 2: with single pointer head