1 Node *unitelist(Node *r1, Node *r2)
2 {
3 if (r1)
4 {
5 if (!r2)
6 {
7 return r1;
8 }
9 }
10 else
11 {
12 return r2;
13 }
14
15 Node *p1 = r1->next, *q1 = r1, *p2 = r2->next;
16
17 while (p1 && p2)
18 {
19 if (p2->data < p1->data)
20 {
21 q1->next = p2;
22 p2 = p2->next;
23 q1->next->next = p1;
24 q1 = q1->next;
25 }
26 else
27 {
28 p1 = p1->next;
29 q1 = q1->next;
30 }
31 }
32
33 if (!p1)
34 {
35 q1->next = p2;
36 }
37
38 free(r2);
39 return r1;
40 }
r1和r2分別是兩個包含空頭節點的有序(從小到大)鏈表，要求合并兩個鏈表，返回合并后的鏈表頭。
另外還有一個遞歸版本，考慮兩個無空頭節點的鏈表，代碼比較簡單：
1 node *merge_list(node *first, node *second)
2 {
3 if (!first) return second;
4 if (!second) return first;
5
6 node *head;
7 if (first->data < second->data)
8 {
9 head = first;
10 head->next = merge_list(first->next, second);
11 }
12 else
13 {
14 head = second;
15 head->next = merge_list(first, second->next);
16 }
17 return head;
18 }
19
posted on 2011-05-02 23:18
myjfm 閱讀(620)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎