题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists.size() == 0) return null;
while (lists.size() > 1) {
if (lists.size() % 2 == 0) {
ArrayList<ListNode> curList = new ArrayList<>();
for (int i = 1; i < lists.size() ; i+=2) {
curList.add(mergeTwoList(lists.get(i),lists.get(i-1)));
}
lists = curList;
} else {
ArrayList<ListNode> curList = new ArrayList<>();
for (int i = 1; i < lists.size() - 1 ; i+=2) {
curList.add(mergeTwoList(lists.get(i),lists.get(i-1)));
}
curList.add(lists.get(lists.size() - 1));
lists = curList;
}
}
return lists.get(0);
}
public ListNode mergeTwoList(ListNode root1,ListNode root2) {
ListNode work = new ListNode(-101);
work.next = null;
ListNode vHead = work;
while (root1 != null && root2 != null) {
if (root1.val >= root2.val) {
vHead.next = root2;
root2 = root2.next;
vHead = vHead.next;
} else {
vHead.next = root1;
root1 = root1.next;
vHead = vHead.next;
}
}
while (root1 != null) {
vHead.next = root1;
root1 = root1.next;
vHead = vHead.next;
}
while (root2 != null) {
vHead.next = root2;
root2 = root2.next;
vHead = vHead.next;
}
return work.next;
}
}
//分lists的长度奇数和偶数，两两合并
