题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类ArrayList * @return ListNode类 */ public ListNode mergeKLists (ArrayList<ListNode> lists) { // 采用分治思想 // 不断的将链表数组分割直到只有一个链表元素 // 然后进行归并,思路和归并两个有序链表思路相同 return divideMerge(lists, 0, lists.size() - 1); } // 划分合并区间 ListNode divideMerge(ArrayList<ListNode> lists, int left, int right) { if (left > right) { return null; } else if (left == right) { // 中间只有一个元素(链表),进行返回 return lists.get(left); } int mid = (left + right) / 2; // 合并 return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right)); } // 将两个有序链表进行合并 public ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } // 一个虚拟节点,一个哨兵节点 ListNode head = new ListNode(-1); ListNode cur = head; while (list1 != null && list2 != null) { if (list1.val <= list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } // 哪个链表还有剩余,直接连接在后面 if (list1 != null) { cur.next = list1; } else { cur.next = list2; } return head.next; } }
在合并两个有序链表的基础上增加了分而治之的思想,当然也可以遍历集合然后取集合前两个元素进行合并,但是那样耗费的时间太长了。