Given two linked lists, insert nodes of second list into first list at alternate positions of first list.
eg. 1->5->7->3->9
6->10->2->4,
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)