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.