資料結構國立中央大學 2026 第 40 題

The following piece of code is a version of Insertion Sort Algorithm that used a linked list to store the sorted data. Fill in the two blank areas on Lines 14 and 20 to make the insert() function maintain the list as a sorted list in ascending order. Nodes with equal values (val) must be ordered according to their insertion time (the earlier ones are placed before the later ones).

 1  #include <stdio.h>
 2  #include <stdlib.h>
 3  struct Node {
 4      int val;
 5      struct Node* next;
 6  };
 7  struct Node* createNode(int x) {
 8      struct Node* node = (struct Node*)malloc(sizeof(struct Node));
 9      node->val = x;
10      node->next = NULL;
11      return node;
12  }
13  struct Node* insert(struct Node* head,struct Node* item){
14      if(head==NULL || head->val ____ item->val){
15          item->next=head;
16          head=item;
17      }
18      else {
19          struct Node* curr=head;
20          while(curr->next != NULL && curr->next->val ____ item->val) {
21              curr=curr->next;
22          }
23          item->next=curr->next;
24          curr->next=item;
25      }
26      return head;
27  }

標準解析