fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct node {
  5.     int val;
  6.     struct node *next;
  7. };
  8.  
  9. struct node* createNode(int val) {
  10.     struct node* newNode = (struct node*) malloc(sizeof(struct node));
  11.     newNode->val = val;
  12.     newNode->next = NULL;
  13.     return newNode;
  14. }
  15.  
  16. void printList(struct node* head) {
  17.     while (head != NULL) {
  18.         printf("%d ", head->val);
  19.         head = head->next;
  20.     }
  21.     printf("\n");
  22. }
  23.  
  24. struct node* merge(struct node* list1, struct node* list2) {
  25.     struct node* ans = (struct node*) malloc(sizeof(struct node));
  26.     struct node* head = ans;
  27.  
  28.     while (list1 != NULL && list2 != NULL) {
  29.         if (list1->val < list2->val) {
  30.             ans->next = list1;
  31.             list1 = list1->next;
  32.             ans = ans->next;
  33.         }
  34.         else if (list1->val == list2->val) {
  35.             ans->next = list1;
  36.             ans = ans->next;
  37.             list1 = list1->next;
  38.             list2 = list2->next;
  39.         }
  40.         else {
  41.             ans->next = list2;
  42.             list2 = list2->next;
  43.             ans = ans->next;
  44.         }
  45.     }
  46.  
  47.     for (; list1; list1 = list1->next) {
  48.         ans->next = list1;
  49.         ans = ans->next;
  50.     }
  51.  
  52.     for (; list2; list2 = list2->next) {
  53.         ans->next = list2;
  54.         ans = ans->next;
  55.     }
  56.  
  57.     struct node* temp = head->next; // 跳過 dummy 頭節點
  58.     free(head); // 釋放 dummy node 記憶體
  59.     return temp;
  60. }
  61.  
  62. int main() {
  63.     // 建立 list1: 1 -> 3 -> 5
  64.     struct node* list1 = createNode(1);
  65.     list1->next = createNode(3);
  66.     list1->next->next = createNode(5);
  67.  
  68.     // 建立 list2: 2 -> 4 -> 6 -> 8
  69.     struct node* list2 = createNode(2);
  70.     list2->next = createNode(4);
  71.  
  72.     list2->next->next = createNode(6);
  73.     list2->next->next->next = createNode(8);
  74.     list2->next->next->next -> next = createNode(18);
  75.  
  76.     printf("list1: ");
  77.     printList(list1);
  78.  
  79.     printf("list2: ");
  80.     printList(list2);
  81.  
  82.     // 合併 list1 和 list2
  83.     struct node* merged = merge(list1, list2);
  84.  
  85.     printf("merged list: ");
  86.     printList(merged);
  87.  
  88.     return 0;
  89. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
list1: 1 3 5 
list2: 2 4 6 8 18 
merged list: 1 2 3 4 5 6 8 18
https://ideone.com/cpIOg8
language:
C (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!