Comment on page
Reverse Linked List
* Step 0: ListNode* prev = NULL;
* ListNode* next = NULL;
* ListNode* curr = head;
*
* curr head
* v v
* NULL "1" -> "2" -> "3" -> NULL
* prev^ ^next
*
*
* Step 1: next = curr->next;
*
* curr head
* v v
* NULL "1" -> "2" -> "3" -> NULL
* prev^ ^next
*
*
* Step 2: curr->next = prev;
*
* curr head
* v v
* NULL <-- "1" "2" -> "3" -> NULL
* prev^ ^next
*
*
* Step 3: prev = curr;
* curr = next;
*
* head curr
* v v
* NULL <-- "1" "2" -> "3" -> NULL
* prev^ ^next
#include <stdio.h>
#include <stdlib.h>
struct Node{
struct Node* next;
int val;
};
void reverse(struct Node **head){
struct Node* prev = NULL;
struct Node* next = NULL;
struct Node* now = *head;
while(now != NULL){
next = now->next;
now->next = prev;
prev = now;
now = next;
}
*head = prev;
}
void enqueue(struct Node **root, int value){
struct Node* new_node = (struct Node*) malloc (sizeof(struct Node));
new_node->val = value;
new_node->next = *root;
*root = new_node;
}
void traverse(struct Node* ref){
struct Node* tmp = ref;
while(tmp!= NULL){
printf("%d\n", tmp->val);
tmp = tmp->next;
}
}
Test code:
int main() {
struct Node* root = NULL;
enqueue(&root, 0);
enqueue(&root, 1);
enqueue(&root, 2);
enqueue(&root, 3);
enqueue(&root, 4);
traverse(root);
reverse(&root);
traverse(root);
return 0;
}
void reverse(struct Node *head){
struct Node* prev = NULL;
struct Node* next = NULL;
struct Node* now = head;
while(now != NULL){
next = now->next;
now->next = prev;
prev = now;
now = next;
}
head = prev;
}