Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
|
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 |
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public
class Solution { public
ListNode mergeKLists(ArrayList<ListNode> lists) { ListNode head = null; if(!lists.isEmpty()){ while(lists.size() > 1){ ListNode first = lists.remove(0); ListNode second = lists.remove(0); ListNode newNode = merge2Lists(first, second); lists.add(0, newNode); } head = lists.get(0); } return
head; } public
ListNode merge2Lists(ListNode first, ListNode second){ ListNode head = new
ListNode(0); ListNode nextNode = head; while(first != null
&& second != null){ if(first.val <= second.val){ nextNode.next = first; first = first.next; nextNode = nextNode.next; } else{ nextNode.next = second; second = second.next; nextNode = nextNode.next; } } if(first == null) nextNode.next = second; else nextNode.next = first; head = head.next; return
head; }} |
leetcode--Merge k Sorted Lists
原文：http://www.cnblogs.com/averillzheng/p/3542331.html