Reversing alternate K elements in a linked list

Hi guys,

The more we work , the more confident we will be.

This post is on reversing alternate k nodes in a linked list. I’m sure this exercise would have be posted in many of the technical blogs but still, lets have a good grasp on how to handle a linked list.

Its quite simple. As you can see in the following image, the first three nodes in the original linked list are reversed, the next three nodes are left just the way they were and the third set of three elements are reversed again. Doesn’t it seem quite fascinating?

chunk_alternative

Practising these kind of exercises will make one stronger in linked list and also helps one  in getting optimal solutions for any such complicated problem.

Well the logic used here is as simple as that. Please look at the following algorithm

Algorithm:

Reverse_K_nodes(head,k) // here k is the number of nodes in the linked list and head is the head node of the linked list

1.Reverse the first k nodes

2.Make  kth node of the reversed list as the head node  and point the next of the first node(head) to k+1th node of the original list.

3.make the current pointer to skip k nodes

4.call the Reverse_K_nodes recursively for the remaiing n-2k nodes

5.return the head node of the linked list

 

Code


#include <stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* next; //pointer that points to the next node of the linked list

};
/*Insert elements into linked list in a FIFO manner*/
void push(struct node** head,int value)
{
struct node* var=(struct node *)malloc(sizeof (struct node));
struct node* run;
var->data=value;
if(*head==NULL)
{
*head=var;
(*head)->next=NULL;
run=(*head);
}
else
{
run->next=var;
run=run->next;

}
}
/* every k elements in the linked list are reversed */
struct node* Reverse_K_nodes(struct node* head,int k)
{
struct node* current=head; //first node
struct node* run;
struct node* prev=NULL;
int count=0;

/*Original list :

1->2->3->4->5->6->7->8->9->NULL

*/
while(count<k && current!=NULL)
{
run=current->next; //assigning the second node  to run
current->next=prev; // first node pointing to its previous node
prev=current; //assigning first node as the previous node
current=run;// assigning the second node as the first node
count++;
}

/* now this is how the modified lists look like

NULL<-1<-2<-3     4->5->6->7->8->9->NULL

i.e., 3->2->1->NULL   4->5->6->7->8->9->NULL

here 1 is the head node 4 is the current node

Combining them using the following code*/

if(head!=NULL)
head->next=current;

/*

3->2->1->4->5->6->7->8->9->NULL

Skipping k elements hereafter */

&nbsp;

&nbsp;

count=0;
while(count<k-1 && current!=NULL)
{
current=current->next;
count++;
}

/*

3->2->1->4->5->6->7->8->9->NULL

here the current->next pointers to node 7 . Here the Reverse_K_nodes function is called recursively*/
if(current!=NULL)
current->next=Reverse_K_nodes(current->next,k);

return prev;

}

void print_list(struct node* ptr)
{
while(ptr!=NULL)
{
printf("%d->",ptr->data);
ptr=ptr->next;
}
printf("NULL");
}
void main()
{
struct node* head;
printf("Original linked list\n");
push(&head,1);
push(&head,2);
push(&head,3);
push(&head,4);
push(&head,5);
push(&head,6);
push(&head,7);
push(&head,8);
push(&head,9);
push(&head,10);
push(&head,11);
push(&head,12);
push(&head,13);
push(&head,14);
push(&head,15);
print_list(head);
head=Reverse_K_nodes(head,5);
printf("\n\n");
printf("Reversing alternate k=5 elements in the linked list\n");
print_list(head);

}

 

OUTPUT

Original linked list
1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->NULL

Reversing alternate k=5 elements in the linked list
3->2->1->4->5->6->9->8->7->10->11->12->15->14->13->NULL

Any doubts or suggestion please do leave me a comment.
Work on reversing strings/sentences using linked list and implement more complex exercises on them.

 

Latest posts by abirami vijayakumar (see all)

Leave a Reply

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