We have two linked lists, insert nodes of the second list into the first list at substitute positions of the first list.
Example :
if first list is 1->2->3 and second is 12->10->2->4->6, the first list should become 1->12->2->10->17->3->2->4->6 and second list should become empty. The nodes of the second list should only be inserted when there are positions available.
Use of extra space is not allowed i.e., insertion must be done in a place. Predictable time complexity is O(n) where n is number of nodes in first list.
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void push(struct Node ** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(struct Node *head)
{
struct Node *temp = head;
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void merge(struct Node *p, struct Node **q)
{
struct Node *p_curr = p, *q_curr = *q;
struct Node *p_next, *q_next;
while (p_curr != NULL && q_curr != NULL)
{
p_next = p_curr->next;
q_next = q_curr->next;
q_curr->next = p_next;
p_curr->next = q_curr;
p_curr = p_next;
q_curr = q_next;
}
*q = q_curr;
}
int main()
{
struct Node *p = NULL, *q = NULL;
push(&p, 3);
push(&p, 2);
push(&p, 1);
printf("I Linked List:\n");
printList(p);
push(&q, 8);
push(&q, 7);
push(&q, 6);
push(&q, 5);
push(&q, 4);
printf("II Linked List:\n");
printList(q);
merge(p, &q);
printf("Updated I Linked List:\n");
printList(p);
printf("Updated II Linked List:\n");
printList(q);
getchar();
return 0;
} ​
Output :
I Linked List:
1 2 3
II Linked List:
4 5 6 7 8
Updated I Linked List:
1 4 2 5 3 6
Updated II Linked List:
7 8
