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 阅读(611)
评论(0) 编辑 收藏 引用 所属分类:
算法基础