-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode_23.c
62 lines (53 loc) · 1.45 KB
/
Leetcode_23.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if (!list1)
return list2;
if (!list2)
return list1;
struct ListNode *mergedHead, *cur1, *cur2, *mergedTail;
cur1 = list1;
cur2 = list2;
if (cur1->val < cur2->val) {
mergedHead = cur1;
mergedTail = cur1;
cur1 = cur1->next;
} else {
mergedHead = cur2;
mergedTail = cur2;
cur2 = cur2->next;
}
while(cur1 && cur2) {
if (cur1->val < cur2->val) {
mergedTail->next = cur1;
mergedTail = mergedTail->next;
cur1 = cur1->next;
} else {
mergedTail->next = cur2;
mergedTail = mergedTail->next;
cur2 = cur2->next;
}
}
if (cur1)
mergedTail->next = cur1;
if (cur2)
mergedTail->next = cur2;
return mergedHead;
}
struct ListNode *merge(struct ListNode **lists, int begin, int end) {
if (begin > end)
return NULL;
if (begin == end)
return lists[begin];
struct ListNode *left = merge(lists, begin, (begin+end)/2);
struct ListNode *right = merge(lists, (begin+end)/2 + 1, end);
return mergeTwoLists(left, right);
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
return merge(lists, 0, listsSize - 1);
}