合并兩個有序的單鏈表
http://www.shnenglu.com/jake1036/archive/2011/06/15/148692.html
1 #include <iostream>
2 using namespace std;
3
4 struct node
5 {
6 int data;
7 node* next;
8 };
9
10 void clear(node* head)
11 {
12 node* t = head->next, * p;
13 while (t != 0)
14 {
15 p = t;
16 t = t->next;
17 delete p;
18 }
19 delete head;
20 }
21
22 void print(node* head)
23 {
24 while (head->next != 0)
25 {
26 cout << head->next->data << ' ';
27 head = head->next;
28 }
29 cout << endl;
30 }
31
32 node* init()
33 {
34 node* ret = new node;
35 ret->next = 0;
36 return ret;
37 }
38
39 node* build(node* head, int item)
40 {
41 node* t = new node;
42 t->next = 0;
43 t->data = item;
44 head->next = t;
45 return t;
46 }
47
48 node* merge(node* h, node* h1, node* h2)
49 {
50 h1 = h1->next;
51 h2 = h2->next;
52 node* t;
53 while (h1 != 0 && h1 != 0)
54 {
55 if (h1->data < h2->data)
56 {
57 t = new node;
58 t->data = h1->data;
59 t->next = 0;
60 h->next = t;
61 h = h->next;
62
63 h1 = h1->next;
64 }
65 else if (h1->data > h2->data)
66 {
67 t = new node;
68 t->data = h2->data;
69 t->next = 0;
70 h->next = t;
71 h = h->next;
72
73 h2 = h2->next;
74 }
75 else
76 {
77 t = new node;
78 t->data = h1->data;
79 t->next = 0;
80 h->next = t;
81 h = h->next;
82 t = new node;
83 t->data = h2->data;
84 t->next = 0;
85 h->next = t;
86 h = h->next;
87
88 h1 = h1->next;
89 h2 = h2->next;
90 }
91 }
92 while (h1 != 0)
93 {
94 t = new node;
95 t->data = h1->data;
96 t->next = 0;
97 h->next = t;
98 h = h->next;
99
100 h1 = h1->next;
101 }
102 while (h2 != 0)
103 {
104 t = new node;
105 t->data = h2->data;
106 t->next = 0;
107 h->next = t;
108 h = h->next;
109
110 h2 = h2->next;
111 }
112
113 return h;
114 }
115
116 int main()
117 {
118 node* h1 = init(), * h2 = init();
119 node* t = h1;
120 for (int i = 1; i <= 10; i += 2)
121 {
122 t = build(t, i);
123 }
124 t = h2;
125 for (int i = 0; i <= 10; i += 2)
126 {
127 t = build(t, i);
128 }
129 print(h1);
130 print(h2);
131
132 node* h = init();
133
134 merge(h, h1, h2);
135
136 print(h);
137
138 clear(h1);
139 clear(h2);
140 clear(h);
141 }
posted on 2011-07-31 18:25
unixfy 閱讀(585)
評論(0) 編輯 收藏 引用