public
Last active

Reverse a singly linked list in C.

  • Download Gist
reverse.c
C
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
// http://stackoverflow.com/questions/1801549/reverse-a-singly-linked-list
 
#include <stdio.h>
#include <assert.h>
 
typedef struct node Node;
struct node {
int data;
Node *next;
};
 
void spec_reverse();
Node *reverse(Node *head);
 
int main()
{
spec_reverse();
return 0;
}
 
void print(Node *head) {
while (head) {
printf("[%d]->", head->data);
head = head->next;
}
printf("NULL\n");
}
 
void spec_reverse() {
// Create a linked list.
// [0]->[1]->[2]->NULL
Node node2 = {2, NULL};
Node node1 = {1, &node2};
Node node0 = {0, &node1};
Node *head = &node0;
 
print(head);
head = reverse(head);
print(head);
 
assert(head == &node2);
assert(head->next == &node1);
assert(head->next->next == &node0);
 
printf("Passed!");
}
 
// Step 1:
//
// prev head next
// | | |
// v v v
// NULL [0]->[1]->[2]->NULL
//
// Step 2:
//
// prev head next
// | | |
// v v v
// NULL<-[0] [1]->[2]->NULL
//
Node *reverse(Node *head)
{
Node *prev = NULL;
Node *next;
 
while (head) {
next = head->next;
head->next = prev;
prev = head;
head = next;
}
 
return prev;
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.