#include <stdio.h>
#include <stdlib.h>
// A nexted list node
struct Node
{
int data;
struct Node *next;
};
/* Function to insert a node at the beginning */
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;
}
/* Utility function to print a singly linked list */
void printList(struct Node *head)
{
struct Node *temp = head;
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Main function that inserts nodes of linked list q into p at
// alternate positions. Since head of first list never changes
// and head of second list may change, we need single pointer
// for first list and double pointer for second list.
void merge(struct Node *p, struct Node **q)
{
struct Node *p_curr = p, *q_curr = *q;
struct Node *p_next, *q_next;
// While there are available positions in p
while (p_curr != NULL && q_curr != NULL)
{
// Save next pointers
p_next = p_curr->next;
q_next = q_curr->next;
// Make q_curr as next of p_curr
q_curr->next = p_next; // Change next pointer of q_curr
p_curr->next = q_curr; // Change next pointer of p_curr
// Update current pointers for next iteration
p_curr = p_next;
q_curr = q_next;
}
*q = q_curr; // Update head pointer of second list
}
// Driver program to test above functions
int main()
{
struct Node *p = NULL, *q = NULL;
push(&p, 3);
push(&p, 2);
push(&p, 1);
printf("First Linked List:\n");
printList(p);
push(&q, 8);
push(&q, 7);
push(&q, 6);
push(&q, 5);
push(&q, 4);
printf("Second Linked List:\n");
printList(q);
merge(p, &q);
printf("Modified First Linked List:\n");
printList(p);
printf("Modified Second Linked List:\n");
printList(q);
getchar();
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KICAKLy8gQSBuZXh0ZWQgbGlzdCBub2RlCnN0cnVjdCBOb2RlCnsKICAgIGludCBkYXRhOwogICAgc3RydWN0IE5vZGUgKm5leHQ7Cn07CiAgCi8qIEZ1bmN0aW9uIHRvIGluc2VydCBhIG5vZGUgYXQgdGhlIGJlZ2lubmluZyAqLwp2b2lkIHB1c2goc3RydWN0IE5vZGUgKiogaGVhZF9yZWYsIGludCBuZXdfZGF0YSkKewogICAgc3RydWN0IE5vZGUqIG5ld19ub2RlID0gCiAgICAgICAgICAgKHN0cnVjdCBOb2RlKikgbWFsbG9jKHNpemVvZihzdHJ1Y3QgTm9kZSkpOwogICAgbmV3X25vZGUtPmRhdGEgID0gbmV3X2RhdGE7CiAgICBuZXdfbm9kZS0+bmV4dCA9ICgqaGVhZF9yZWYpOwogICAgKCpoZWFkX3JlZikgID0gbmV3X25vZGU7Cn0KICAKLyogVXRpbGl0eSBmdW5jdGlvbiB0byBwcmludCBhIHNpbmdseSBsaW5rZWQgbGlzdCAqLwp2b2lkIHByaW50TGlzdChzdHJ1Y3QgTm9kZSAqaGVhZCkKewogICAgc3RydWN0IE5vZGUgKnRlbXAgPSBoZWFkOwogICAgd2hpbGUgKHRlbXAgIT0gTlVMTCkKICAgIHsKICAgICAgICBwcmludGYoIiVkICIsIHRlbXAtPmRhdGEpOwogICAgICAgIHRlbXAgPSB0ZW1wLT5uZXh0OwogICAgfQogICAgcHJpbnRmKCJcbiIpOwp9CiAgCi8vIE1haW4gZnVuY3Rpb24gdGhhdCBpbnNlcnRzIG5vZGVzIG9mIGxpbmtlZCBsaXN0IHEgaW50byBwIGF0IAovLyBhbHRlcm5hdGUgcG9zaXRpb25zLiBTaW5jZSBoZWFkIG9mIGZpcnN0IGxpc3QgbmV2ZXIgY2hhbmdlcyAKLy8gYW5kIGhlYWQgb2Ygc2Vjb25kIGxpc3QgIG1heSBjaGFuZ2UsIHdlIG5lZWQgc2luZ2xlIHBvaW50ZXIKLy8gZm9yIGZpcnN0IGxpc3QgYW5kIGRvdWJsZSBwb2ludGVyIGZvciBzZWNvbmQgbGlzdC4Kdm9pZCBtZXJnZShzdHJ1Y3QgTm9kZSAqcCwgc3RydWN0IE5vZGUgKipxKQp7CiAgICAgc3RydWN0IE5vZGUgKnBfY3VyciA9IHAsICpxX2N1cnIgPSAqcTsKICAgICBzdHJ1Y3QgTm9kZSAqcF9uZXh0LCAqcV9uZXh0OwogIAogICAgIC8vIFdoaWxlIHRoZXJlIGFyZSBhdmFpbGFibGUgcG9zaXRpb25zIGluIHAKICAgICB3aGlsZSAocF9jdXJyICE9IE5VTEwgJiYgcV9jdXJyICE9IE5VTEwpCiAgICAgewogICAgICAgICAvLyBTYXZlIG5leHQgcG9pbnRlcnMKICAgICAgICAgcF9uZXh0ID0gcF9jdXJyLT5uZXh0OwogICAgICAgICBxX25leHQgPSBxX2N1cnItPm5leHQ7CiAgCiAgICAgICAgIC8vIE1ha2UgcV9jdXJyIGFzIG5leHQgb2YgcF9jdXJyCiAgICAgICAgIHFfY3Vyci0+bmV4dCA9IHBfbmV4dDsgIC8vIENoYW5nZSBuZXh0IHBvaW50ZXIgb2YgcV9jdXJyCiAgICAgICAgIHBfY3Vyci0+bmV4dCA9IHFfY3VycjsgIC8vIENoYW5nZSBuZXh0IHBvaW50ZXIgb2YgcF9jdXJyCiAgCiAgICAgICAgIC8vIFVwZGF0ZSBjdXJyZW50IHBvaW50ZXJzIGZvciBuZXh0IGl0ZXJhdGlvbgogICAgICAgICBwX2N1cnIgPSBwX25leHQ7CiAgICAgICAgIHFfY3VyciA9IHFfbmV4dDsKICAgIH0KICAKICAgICpxID0gcV9jdXJyOyAvLyBVcGRhdGUgaGVhZCBwb2ludGVyIG9mIHNlY29uZCBsaXN0Cn0KICAKLy8gRHJpdmVyIHByb2dyYW0gdG8gdGVzdCBhYm92ZSBmdW5jdGlvbnMKaW50IG1haW4oKQp7CiAgICAgc3RydWN0IE5vZGUgKnAgPSBOVUxMLCAqcSA9IE5VTEw7CiAgICAgcHVzaCgmcCwgMyk7CiAgICAgcHVzaCgmcCwgMik7CiAgICAgcHVzaCgmcCwgMSk7CiAgICAgcHJpbnRmKCJGaXJzdCBMaW5rZWQgTGlzdDpcbiIpOwogICAgIHByaW50TGlzdChwKTsKICAKICAgICBwdXNoKCZxLCA4KTsKICAgICBwdXNoKCZxLCA3KTsKICAgICBwdXNoKCZxLCA2KTsKICAgICBwdXNoKCZxLCA1KTsKICAgICBwdXNoKCZxLCA0KTsKICAgICBwcmludGYoIlNlY29uZCBMaW5rZWQgTGlzdDpcbiIpOwogICAgIHByaW50TGlzdChxKTsKICAKICAgICBtZXJnZShwLCAmcSk7CiAgCiAgICAgcHJpbnRmKCJNb2RpZmllZCBGaXJzdCBMaW5rZWQgTGlzdDpcbiIpOwogICAgIHByaW50TGlzdChwKTsKICAKICAgICBwcmludGYoIk1vZGlmaWVkIFNlY29uZCBMaW5rZWQgTGlzdDpcbiIpOwogICAgIHByaW50TGlzdChxKTsKICAKICAgICBnZXRjaGFyKCk7CiAgICAgcmV0dXJuIDA7Cn0=