Delete a Node from LL

Explanation

1
* Step 0: ListNode* prev = NULL;
2
* ListNode* node = *head;
3
​
4
* now head
5
* v v
6
* NULL "0" -> "1" -> "2" -> "3" -> "4" -> NULL
7
* ^prev
8
*
9
*
10
* Step 1: while to find the target: "2";
11
*
12
* head now
13
* v v
14
* "0" -> "1" -> "2" -> "3" -> "4" -> NULL
15
* ^prev
16
*
17
*
18
* Step 2: prev->next = now->next;
19
*
20
* head now
21
* v v
22
* "0" -> "1" -> "2" -> "3" -> "4" -> NULL
23
* ^prev-------> ^next
24
*
25
*
26
* Step 3: free(now)
27
*
28
* head
29
* v
30
* "0" -> "1" -> -> "3" -> "4" -> NULL
31
* ^prev
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 traverse(struct Node** head){
11
struct Node* curr = *head;
12
​
13
while(curr != NULL){
14
printf("Value: %d\n", curr->val);
15
curr = curr->next;
16
}
17
}
18
​
19
​
20
void addNodeToLL(struct Node** head, int val){
21
struct Node* new = (struct Node*) malloc(sizeof(struct Node));
22
new->val = val;
23
new->next = *head;
24
*head = new;
25
}
26
​
27
void deleteNodeToLL(struct Node** head, int val){
28
​
29
struct Node* now = *head;
30
struct Node* prev = NULL;
31
​
32
if(now != NULL && now->val == val){
33
*head = now->next;
34
free(now);
35
}
36
​
37
while(now != NULL && now->val != val){
38
prev = now;
39
now = now->next;
40
}
41
​
42
if(now == NULL){
43
// no any node can be delete
44
return;
45
}
46
​
47
// start to delete
48
prev->next = now->next;
49
free(now);
50
}
51
​
Copied!

Test code

1
int main() {
2
3
struct Node* root = NULL;
4
​
5
addNodeToLL(&root, 0);
6
addNodeToLL(&root, 1);
7
addNodeToLL(&root, 2);
8
addNodeToLL(&root, 3);
9
addNodeToLL(&root, 4);
10
11
traverse(&root);
12
​
13
deleteNodeToLL(&root, 2);
14
traverse(&root);
15
return 0;
16
}
Copied!
Copy link