# 23. Merge k Sorted Lists

![](/files/-MijOB6tapGhh-aZKIWu)

![](/files/-MijODfjVGE9NCHfFpQD)

### solution1 - use divide and conquer

divide and conquer => logk, k is lists\[] length, split to 2 part

merge O(N), N is all nodes in two lists

 , so O(Nlogk)

![](/files/-MijNJTaEY1KxZNusuP9)

**notice**, in this case, **should return null => . output: \[]** 

![](/files/-MijMhFtLOzuM47TzWy9)

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null; // notice this!
        
        return partition(lists, 0, lists.length - 1);
    }
    
    private ListNode partition(ListNode[] lists, int s, int e) {
        if (s == e) {
            return lists[s]; // notice this!
        } else if (s < e) {
            int mid = (s+e)/2;
            ListNode l1 = partition(lists, s, mid);
            ListNode l2 = partition(lists, mid+1, e);
            return merge(l1, l2);
        } else {
            return null; // notice this!
        }
    }
    
    // this part is leetcode 21. Merge Two Sorted Lists
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1); // notice this should new a node
        ListNode pre = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                pre.next = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        pre.next = (l1 == null) ? l2 : l1;
        
        return head.next;
    }
}
```

假設只有兩個數, index 0, 1

所以 mid = 0+1)/2 = 0

l1 = partition(lists, 0,0) = ( s == e return lists\[s] ) =  list\[0]

l2 = partition(lists, 0+1,1) = ( s == e return lists\[s] ) =  list\[1]

return merge(list\[0], list\[1])&#x20;

```java
    private ListNode partition(ListNode[] lists, int s, int e) {
        if (s == e) {
            return lists[s]; // notice this!
        } else if (s < e) {
            int mid = (s+e)/2;
            ListNode l1 = partition(lists, s, mid);
            ListNode l2 = partition(lists, mid+1, e);
            return merge(l1, l2);
        } else {
            return null; // notice this!
        }
    }
```

### solution2 - use priorityQueue

easier solution!

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        
        for (ListNode list : lists) {
            if (list != null) {
                queue.add(list);
            }
        }
        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
            if (cur.next != null) {
                queue.add(cur.next);
            }
        }
        return dummy.next;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/linkedlist/23.-merge-k-sorted-lists.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.