题目链接:
链接
题目描述:
思路:
同步合并
已知顺序排列,每个链表的node比较再加进结果,用优先队列方便比较node,可以先把每个链表的头结点加进队列,然后队列头出,出来的头还有next,就加进去,这样确保每个链表都有节点放进队列里面了
两两合并
两两合并链表,逐个击破
实现代码:
class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists == null || lists.length == 0){return null;}PriorityQueue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);;for(ListNode node : lists){if (node != null) {q.offer(node);}}ListNode dummy = new ListNode(0);ListNode cur = dummy;while(!q.isEmpty()){cur.next = q.poll();cur = cur.next; if(cur.next != null){q.offer(cur.next);}}return dummy.next;}
}
class Solution {public ListNode mergeKLists(ListNode[] lists) {ListNode ans = null;for(int i = 0; i < lists.length ; i++){ans = merge(ans,lists[i]);}return ans;}public ListNode merge(ListNode a, ListNode b){if(a == null || b== null){return a != null ? a:b;}ListNode head = new ListNode(0);ListNode cur = head, p1 = a, p2 = b;while(p1 != null && p2 != null){if(p1.val < p2.val){cur.next = p1;p1 = p1.next;}else{cur.next = p2;p2 = p2.next;}cur = cur.next;}cur.next = p1 != null ? p1 : p2;return head.next;}
}