Merge a linked list into another linked list at alternate positions

Given two linked lists, insert nodes of second list into first list at alternate positions of first list.
eg. 1->5->7->3->9
the first list should become 1->6->5->10->7->2->3->4->9 and second list should become empty.
The nodes of second list should only be inserted when there are positions available.
If the first list is 1->2->3 and second list is 4->5->6->7, then first list should become 1->4->2->5->3->6 and second list to 7.

This problem can be implemented using recursion too. Here iterative approach is explained. Recursive readers should try.

#include <stdio.h>
#include <stdlib.h>
// A nexted list node
struct node
    int data;
    struct node *next;

void mergeAtAlternatePos(struct node *p, struct node *q)
     struct node *first = p, *sec = q;
     struct node *first_next, *sec_next;
     // While there are avialable positions in p
     while (first != NULL && sec != NULL)
         first_next = first->next;
         sec_next = sec->next;
         sec->next = first_next;  
         first->next = sec;
         first = first_next;
         sec = sec_next;
// Update start pointer of second list
    *q = sec; 

Time compleixty: O(N)

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