How to reverse a singly linked list ?
This problem demonstrates the ability to work with pointers and visualize a data structure. Here we are using two pointers to reverse a list.
#include <stdio.h>
// The list element type and head.
struct node {
int data;
struct node *link;
};
static struct node *first = NULL;
// A reverse function which uses only two extra pointers.
void reverse(){
// curNode traverses the list, first is reset to empty list.
struct node *curNode = first, *nxtNode;
first = NULL;
// Until no more in list, insert current before first and advance.
while (curNode != NULL) {
// Need to save next node since we're changing the current.
nxtNode = curNode->link;
// Insert at start of new list.
curNode->link = first;
first = curNode;
// Advance to next.
curNode = nxtNode;
}
}
// Code to print the current list.
static void printNodes(){
struct node *curNode = first;
while (curNode != NULL) {
printf ("%d\n", curNode->data);
curNode = curNode->link;
}
}
// main program.
int main (void) {
int i;
struct node *newnode;
// Create list (using actually the same insert-before-first
// that is used in reverse function.
for (i = 0; i < 5; i++){
newnode = malloc (sizeof (struct node));
newnode->data = i;
newnode->link = first;
first = newnode;
}
// print list, reverse it, then print again.
printNodes();
reverse();
printNodes();
return 0;
}
Time complexity will be O(n) as you have to visit every node to change the pointers.
