fork download
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // A nexted list node
  5. struct Node
  6. {
  7. int data;
  8. struct Node *next;
  9. };
  10.  
  11. /* Function to insert a node at the beginning */
  12. void push(struct Node ** head_ref, int new_data)
  13. {
  14. struct Node* new_node =
  15. (struct Node*) malloc(sizeof(struct Node));
  16. new_node->data = new_data;
  17. new_node->next = (*head_ref);
  18. (*head_ref) = new_node;
  19. }
  20.  
  21. /* Utility function to print a singly linked list */
  22. void printList(struct Node *head)
  23. {
  24. struct Node *temp = head;
  25. while (temp != NULL)
  26. {
  27. printf("%d ", temp->data);
  28. temp = temp->next;
  29. }
  30. printf("\n");
  31. }
  32.  
  33. // Main function that inserts nodes of linked list q into p at
  34. // alternate positions. Since head of first list never changes
  35. // and head of second list may change, we need single pointer
  36. // for first list and double pointer for second list.
  37. void merge(struct Node *p, struct Node **q)
  38. {
  39. struct Node *p_curr = p, *q_curr = *q;
  40. struct Node *p_next, *q_next;
  41.  
  42. // While there are available positions in p
  43. while (p_curr != NULL && q_curr != NULL)
  44. {
  45. // Save next pointers
  46. p_next = p_curr->next;
  47. q_next = q_curr->next;
  48.  
  49. // Make q_curr as next of p_curr
  50. q_curr->next = p_next; // Change next pointer of q_curr
  51. p_curr->next = q_curr; // Change next pointer of p_curr
  52.  
  53. // Update current pointers for next iteration
  54. p_curr = p_next;
  55. q_curr = q_next;
  56. }
  57.  
  58. *q = q_curr; // Update head pointer of second list
  59. }
  60.  
  61. // Driver program to test above functions
  62. int main()
  63. {
  64. struct Node *p = NULL, *q = NULL;
  65. push(&p, 3);
  66. push(&p, 2);
  67. push(&p, 1);
  68. printf("First Linked List:\n");
  69. printList(p);
  70.  
  71. push(&q, 8);
  72. push(&q, 7);
  73. push(&q, 6);
  74. push(&q, 5);
  75. push(&q, 4);
  76. printf("Second Linked List:\n");
  77. printList(q);
  78.  
  79. merge(p, &q);
  80.  
  81. printf("Modified First Linked List:\n");
  82. printList(p);
  83.  
  84. printf("Modified Second Linked List:\n");
  85. printList(q);
  86.  
  87. getchar();
  88. return 0;
  89. }
Success #stdin #stdout 0s 5472KB
stdin
45
stdout
First Linked List:
1 2 3 
Second Linked List:
4 5 6 7 8 
Modified First Linked List:
1 4 2 5 3 6 
Modified Second Linked List:
7 8