Skip to main content

Reverse a singly linked list

One of the commonly used interview question is - how do you reverse a linked list?

If you talk about a recursive function to print the list in reverse order, you are so wrong. The question is to reverse the nodes of list. Not print the nodes in reverse order.

So how do you go about reversing the nodes.

You need to take each node and link it to previous node. But a singly linked list does not have previous pointer.

So if n1 is current node, n2 = n1->next, you should set

    n2->next = NULL

But doing this would cut off the list at n2.

So the solution is recursion. That is to reverse n nodes  n1,n2,n3... of a list,
  • reverse the sub list from n2,n3,n4....
  • link n2->next to n1
  • set n1->next to NULL
The last step is necessary because, once we reverse the list, first node must become last node and should be pointing to NULL.

But now the difficulty is regarding the head? Where is head and how do we set it?

Once we reach end of list  viz n1->next ==NULL, this node must become new head of the list. We have to store it in a static variable, in order not to change it. 
  1. set current node =n1
  2. if lastnode set head =n1
  3. set node2 = nextnode
  4. recursively reverse list from node2 to end of list
  5. set node2->next = l1
  6. set l1->next = NULL
And here is reverse function


NODEPTR reverse_list(NODEPTR l1)
{
static NODEPTR head;
if(l1->next==NULL)
{
head = l1;
return l1;
}
else
{
NODEPTR node2 = l1->next;
reverse_list(node2);
node2->next = l1;
l1->next = NULL;
return head;
}
}

And this is the complete program.


#include<stdio.h>  
#include<stdlib.h>
struct node
{
int n;
struct node *next;
};
typedef struct node * NODEPTR;

NODEPTR create_node(int value)
{
NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));
temp->next = NULL;
temp->n = value;
return temp;
}

NODEPTR append_node(NODEPTR head, NODEPTR newnode)
{
NODEPTR temp = head;
if(temp==NULL)
return newnode;
while(temp->next !=NULL)
temp = temp->next;
temp->next = newnode;
return head;
}

void display_nodes(NODEPTR head)
{
NODEPTR temp = head;//redundant
while (temp!= NULL)
{
printf("%d====>",temp->n);
temp = temp->next;
}
printf("\n");
}

NODEPTR reverse_list(NODEPTR l1)
{
static NODEPTR head;
if(l1->next==NULL)
{
head = l1;
return l1;
}
else
{
NODEPTR node2 = l1->next;
reverse_list(node2);
node2->next = l1;
l1->next = NULL;
return head;
}
}

NODEPTR delete_node(NODEPTR head, NODEPTR dnode)
{
NODEPTR temp = head;
NODEPTR prev = NULL;
if(dnode==head)
{
head = head->next;
}
while (temp !=NULL && temp!=dnode)
{
prev = temp;
temp = temp->next;
}

if(prev!=NULL)
{
prev->next = temp->next;
}

free(dnode);
return head;
}

int main()
{
NODEPTR head;
NODEPTR newnode,dnode;
int numnodes,i;
//initialize head
head = NULL;
printf("Number of nodes = ");
scanf("%d",&numnodes);

for(i = 0;i<numnodes;i++)
{
int value;
NODEPTR newnode;
printf("node value=");
scanf("%d",&value);
newnode = create_node(value);
head = append_node(head,newnode);
}
printf("The linked list now is ");
display_nodes(head);
head = reverse_list(head);
printf("Now the list is ");
display_nodes(head);
}

You can download the program from here.

Comments

Popular posts from this blog

In order traversal of nodes in the range x to y

Question : Write a function for in-order traversal of nodes in the range x to y from a binary search tree. This is quite a simple function. As a first solution we can just traverse our binary search tree in inorder and display only the nodes which are in the range x to y. But if the current node has a value less than x, do we have to traverse its left subtree? No. Because all the nodes in left subtree will be smaller than x. Similarly if the current node has a key value more than y, we need not visit its right subtree. Now we are ready to write our algorithm.     if nd is NOT NULL  if nd->val >=x then visit all the nodes of left subtree of nd recursively display nd->val if nd->val <y then visit all the nodes of right subtree of nd recursively  That's all. We have our function ready. void in_order_middle (NODEPTR nd, int x, int y) { if (nd) { if (nd -> val >= x) in_order_middle(nd...

Josephus problem

Question: Write a function to delete every k th node from circular linked list until only one node is left. This has a story associated with it. Flavius Josephus was Jewish Historian from 1st century. He and 40 other soldiers were trapped in a cave by Romans. They decided to kill themselves rather than surrendering to Romans. Their method was like this. All the soldiers will stand in a circle and every k th soldier will be shot dead. Josephus said to have calculated the starting point so that he would remain alive. So we have similar problem at hand. We delete every kth node in a circular list. Eventually only one node will be left. e.g. Let us say this is our list And we are deleting every third node.  We will delete 30. Then we delete 60. Next we delete 10. Next it will be 50. Next to be deleted is 20. Next 80. This continues. Implementation   We can count k-1 nodes and delete next node. This can be repeated in  a loop. What must be the termina...

Lowest common ancestor of binary search tree

Question : Write a function to print the lowest common ancestor of two nodes in a binary search tree.  Lowest common ancestor of two nodes x and y in a binary tree is the lowest node that has both x and y as descendants. Here lowest common ancestor of 1 and 7 is 3. LCA of 13 and 7 is root - 8. And LCA of 6 and 7 is 6 itself. The program to find gets complicated for an ordinary binary tree. But for a binary search tree, it is quite simple. As we see from the diagram above, the paths to 1 and 4 are common till the node 3. And at 3 they branch in different directions. So 3 is our LCA. That is lowest common ancestor is the node where the paths to x and y from root deviate. As long as they branch in same direction, we continue to traverse. When they branch in different directions, that is the lowest common ancestor. So let us write a simple algorithm, set temp=root if temp->val >x and temp->val>y temp = temp->left else if temp->val<x and ...