链表的归并操作

148. Sort List
23. Merge k Sorted Lists

23. Merge k Sorted Lists

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
public ListNode mergeKLists(ListNode[] lists) {
	return sort(lists,0 ,lists.length-1);
}
private ListNode sort(ListNode[] lists, int s ,int e){
	if(s < e){
		int mid = (s + e) / 2;
		ListNode head1 = sort(lists, s, mid);
		ListNode head2 = sort(lists, mid+1, e);
		return merge(head1, head2);
		
	}else if(s == e){
		return lists[s];
	}else{
		return null;
	}
}
private ListNode merge(ListNode a, ListNode b){
	ListNode head = new ListNode(0);
	ListNode cur = head;
	while(a != null && b != null){
		if(a.val < b.val){
			cur.next = a;
			a = a.next;
		}else{
			cur.next = b;
			b = b.next;
		}
		cur = cur.next;
	}
	while(a != null){
		cur.next = a;
		a = a.next;
		cur = cur.next;
	}
	while(b != null){
		cur.next = b;
		b = b.next;
		cur = cur.next;
	}
	
	return head.next;
	
}