Reverse a singly linked list

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.


return 0;

Time complexity will be O(n) as  you have to visit every node to change the pointers.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation