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?
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
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
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;
/* 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;
/*Original list :
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
/* now this is how the modified lists look like
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*/
Skipping k elements hereafter */
while(count<k-1 && current!=NULL)
here the current->next pointers to node 7 . Here the Reverse_K_nodes function is called recursively*/
void print_list(struct node* ptr)
struct node* head;
printf("Original linked list\n");
printf("Reversing alternate k=5 elements in the linked list\n");
Original linked list
Reversing alternate k=5 elements in the linked list
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)