Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // LeetCode URL: https://leetcode.com/problems/add-two-numbers/
- import java.util.PriorityQueue;
- // Definition for singly-linked list.
- class ListNode {
- int val;
- ListNode next;
- ListNode(int x) {
- val = x;
- }
- }
- /**
- * Using Priority Queue
- *
- * Time Complexity: O(N log K)
- *
- * Space Complexity: O(K)
- *
- * N = Total number of all nodes in all lists. K = Number of lists.
- */
- class Solution1 {
- public ListNode mergeKLists(ListNode[] lists) {
- if (lists == null || lists.length == 0) {
- return null;
- }
- if (lists.length == 1) {
- return lists[0];
- }
- PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));
- ListNode dummyNode = new ListNode(-1);
- ListNode prevNode = dummyNode;
- for (ListNode listHead : lists) {
- if (listHead != null) {
- queue.offer(listHead);
- }
- }
- while (!queue.isEmpty()) {
- prevNode.next = queue.poll();
- prevNode = prevNode.next;
- if (prevNode.next != null) {
- queue.offer(prevNode.next);
- }
- }
- return dummyNode.next;
- }
- }
- /**
- * Merge with Divide & Conquer
- *
- * Time Complexity: Divide and Merge operation forms a tree with height log K.
- * Suppose there are N total nodes in all the list.. Thus the total time
- * complexity is O(N * log K)
- *
- * Space Complexity: O(1)
- *
- * N = Total number of all nodes in all lists. K = Number of lists.
- */
- class Solution2 {
- public ListNode mergeKLists(ListNode[] lists) {
- if (lists == null || lists.length == 0) {
- return null;
- }
- if (lists.length == 1) {
- return lists[0];
- }
- int interval = 1; // Interval to find the index of lists to be merged.
- while (interval < lists.length) {
- for (int i = 0; i < lists.length - interval; i += interval * 2) {
- lists[i] = merge2Lists(lists[i], lists[i + interval]);
- }
- interval *= 2;
- }
- return lists[0];
- }
- private ListNode merge2Lists(ListNode l1, ListNode l2) {
- if (l1 == null) {
- return l2;
- }
- if (l2 == null) {
- return l1;
- }
- ListNode dummyHead = new ListNode(-1);
- ListNode prevNode = dummyHead;
- ListNode p = l1;
- ListNode q = l2;
- while (p != null && q != null) {
- if (p.val <= q.val) {
- prevNode.next = p;
- p = p.next;
- } else {
- prevNode.next = q;
- q = q.next;
- }
- prevNode = prevNode.next;
- prevNode.next = null;
- }
- prevNode.next = p == null ? q : p;
- return dummyHead.next;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement