题解 | #合并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的长度奇数和偶数,两两合并