Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

合并K个排序链表

Posted on Edited on In , ,
Symbols count in article: 9.2k Reading time ≈ 8 mins.

来源Leetcode第23题合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:

[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

归并

这题其实之前做过简化版的，合并2个有序链表，这次合并K个，就可以采用K路归并的思路，两两合并有序链表。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)  //合并2个有序链表
{
struct ListNode* l1,*l2,*head,*n;
    l1=p1;
    l2=p2;
    if(l1==NULL)return l2;
    if(l2==NULL)return l1;
    if(l1->val<l2->val)
    {
    head = l1;
    n = head;
    l1=l1->next;
    }
    else
    {
    head = l2;
    n = head;
    l2=l2->next;
    }
    while(l1!=NULL&&l2!=NULL)
    {
        if(l1->val<l2->val)
        {
            head->next=l1;
            l1=l1->next;
            head = head ->next;
        }
        else
        {
            head ->next = l2;
            l2=l2->next;
            head = head ->next;
        }
    }
    if(l1 == NULL)
    {
        head -> next = l2;
    }
    if(l2 == NULL)
    head -> next = l1;
    return n;
}

struct ListNode* _mergeKLists(struct ListNode** lists, int listsSize)
{
	int count;
	struct ListNode* l1, *l2;
	count = listsSize;

	if (count == 0) {
		return NULL;
	} else if (count == 1) {
		return lists[0];
	} else if (count == 2) {
		return mergeTwoLists(lists[0], lists[1]);
	}
 
	l1 = _mergeKLists(&lists[0], (count+1)/2);
	l2 = _mergeKLists(&lists[(count+1)/2], count - (count+1)/2);
  
	return mergeTwoLists(l1, l2);
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{  
	return _mergeKLists(lists, listsSize);
}

接下来我们来看看官方解答

方法1：暴力

想法 & 算法

  • 遍历所有链表，将所有节点的值放到一个数组中。
  • 将这个数组排序，然后遍历所有元素得到正确顺序的值。
  • 用遍历得到的值，创建一个新的有序链表。

不得不吐槽，这排序是怎么做的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        self.nodes = []
        head = point = ListNode(0)
        for l in lists:
            while l:
                self.nodes.append(l.val)
                l = l.next
        for x in sorted(self.nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next

复杂度分析

  • 时间复杂度：O(NlogN) ，其中 NN 是节点的总数目。
    • 遍历所有的值需花费 O(N) 的时间。
    • 一个稳定的排序算法花费 O(NlogN) 的时间。
    • 遍历同时创建新的有序链表花费 O(N) 的时间。
  • 空间复杂度：O(N) 。
    • 排序花费 O(N) 空间（这取决 于你选择的算法）。
    • 创建一个新的链表花费 O(N) 的空间。

方法2：逐一比较

算法

  • 比较 k 个节点（每个链表的首节点），获得最小值的节点。
  • 将选中的节点接在最终有序链表的后面。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeKListsSub(struct ListNode** lists, int listsSize){
    struct ListNode* temp = NULL;
    int val = INT_MAX;
    int pos = -1;
    int i;
    
    for(i = 0; i < listsSize;i++){
        if(lists[i]){
            if(val > lists[i]->val){
                val = lists[i]->val;
                pos = i;
            }
        }
    } //先找到所有链表里最小的元素
    
    if(pos != -1){
        temp = lists[pos];
        lists[pos] = lists[pos]->next; //修改已经找到的最小元素链表的节点，将其指向下一个
        temp->next = mergeKListsSub(lists,listsSize); //递归查找第二个最小的元素
    }
    
    return temp;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    return mergeKListsSub(lists,listsSize);
}

复杂度分析

  • 时间复杂度： O(kN) ，其中 k 是链表的数目。

    • 几乎最终有序链表中每个节点的时间开销都为 O(k) （k-1 次比较）。
    • 总共有 N 个节点在最后的链表中。

  • 空间复杂度：

    • O(n)。创建一个新的链表空间开销为 O(n) 。
    • O(1)。重复利用原来的链表节点，每次选择节点时将它直接接在最后返回的链表后面，而不是创建一个新的节点。

对比初始代码，可以发现时间复杂度明显提升，运行时间也由12ms提升到480ms。

方法3：用优先队列优化方法 2

算法

几乎与上述方法一样，除了将比较环节用 优先队列进行了优化。你可以参考这里 获取更多信息。

代码依旧是Python，摸了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Queue import PriorityQueue

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        head = point = ListNode(0)
        q = PriorityQueue()
        for l in lists:
            if l:
                q.put((l.val, l))
        while not q.empty():
            val, node = q.get()
            point.next = ListNode(val)
            point = point.next
            node = node.next
            if node:
                q.put((node.val, node))
        return head.next

Java实现一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
    ListNode dummy = new ListNode(0);
    ListNode p = dummy;
    queue.addAll(Stream.of(lists).filter(Objects::nonNull).collect(Collectors.toList()));
    while (!queue.isEmpty()) {
        ListNode node = queue.poll();
        p.next = node;
        p = p.next;
        if (node.next != null)
            queue.add(node.next);
    }
    return dummy.next;
}

Java实现二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.util.Comparator;
import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    ListNode(Integer[] nums) {
        ListNode currNode = this;
        currNode.val = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currNode.next = new ListNode(nums[i]);
            currNode = currNode.next;
        }
    }

    @Override
    public String toString() {
        ListNode currNode = this;
        StringBuilder s = new StringBuilder();
        while (currNode != null) {
            s.append(currNode.val);
            s.append(" -> ");
            currNode = currNode.next;
        }
        // 最后添加一个 NULL 标志表示添加到末尾了
        s.append("NULL");
        return s.toString();
    }
}

public class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(len, Comparator.comparingInt(a -> a.val));
        ListNode dummyNode = new ListNode(-1);
        ListNode curNode = dummyNode;
        for (ListNode list : lists) {
            if (list != null) {
                // 这一步很关键，不能也没有必要将空对象添加到优先队列中
                priorityQueue.add(list);
            }
        }
        while (!priorityQueue.isEmpty()) {
            // 优先队列非空才能出队
            ListNode node = priorityQueue.poll();
            // 当前节点的 next 指针指向出队元素
            curNode.next = node;
            // 当前指针向前移动一个元素，指向了刚刚出队的那个元素
            curNode = curNode.next;
            if (curNode.next != null) {
                // 只有非空节点才能加入到优先队列中
                priorityQueue.add(curNode.next);
            }
        }
        return dummyNode.next;
    }

    public static void main(String[] args) {
        Integer[] nums1 = {1, 4, 5};
        Integer[] nums2 = {1, 3, 4};
        Integer[] nums3 = {2, 6};
        ListNode head1 = new ListNode(nums1);
        ListNode head2 = new ListNode(nums2);
        ListNode head3 = new ListNode(nums3);
        ListNode[] lists = new ListNode[3];
        lists[0] = head1;
        lists[1] = head2;
        lists[2] = head3;
        Solution solution = new Solution();
        ListNode mergeKLists = solution.mergeKLists(lists);
        System.out.println(mergeKLists);
    }
}

复杂度分析

  • 时间复杂度： O(Nlogk) ，其中 k 是链表的数目。

    • 弹出操作时，比较操作的代价会被优化到 O(logk) 。同时，找到最小值节点的时间开销仅仅为 O(1)。
    • 最后的链表中总共有 N 个节点。

  • 空间复杂度：

    • O(n)。创造一个新的链表需要 O(n) 的开销。
    • O(k)。以上代码采用了重复利用原有节点，所以只要 O(1) 的空间。同时优先队列（通常用堆实现）需要 O(k) 的空间（远比大多数情况的 NN要小）

最小索引堆实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode mergeKLists(ListNode[] lists) {
       int len = 0;
       if((len=lists.length)==0 || lists == null) return null;
       ListNode preHead = new ListNode(-1);
       ListNode preNode = preHead;
       PriorityQueue<ListNode> queue = new PriorityQueue<>(len, new Comparator<ListNode>() {
           @Override
           public int compare(ListNode o1, ListNode o2) {
               return o1.val - o2.val;
           }
       });
       for (ListNode node : lists) {
           if(node!=null) queue.add(node);
       }
       while(!queue.isEmpty()){
           ListNode small = queue.poll();
           preNode.next = small;
           if(small.next!=null) queue.add(small.next); //将最小值节点后面的节点添加到队里中
           preNode = preNode.next;
       }
       return preHead.next;
   }

方法4：逐一两两合并链表

算法

将合并 k 个链表的问题转化成合并 2 个链表 k-1 次

复杂度分析

  • 时间复杂度： O(kN)，其中 k 是链表的数目。

    • 我们可以在 O(n) 的时间内合并两个有序链表，其中 n 是两个链表的总长度。
    • 把所有合并过程所需的时间加起来，我们可以得到： O(kN)

  • 空间复杂度：O(1)

    • 我们可以在 O(1) 空间内合并两个有序链表。

代码见最开始部分。

方法5：分治

这个方法沿用了上面的解法，但是进行了较大的优化。我们不需要对大部分节点重复遍历多次。

+ 将 k 个链表配对并将同一对中的链表合并。
+ 第一轮合并以后，k 个链表被合并成了 K/2个链表，平均长度为 2N/k，然后是k/4个链表，K/8个链表等等。
+ 重复这一过程，直到我们得到了最终的有序链表。

因此，我们在每一次配对合并的过程中都会遍历几乎全部 N 个节点，并重复这一过程 log2K 次。

代码依旧是Python，摸了,下次补个C或者JAVA的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        amount = len(lists)
        interval = 1
        while interval < amount:
            for i in range(0, amount - interval, interval * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i + interval])
            interval *= 2
        return lists[0] if amount > 0 else lists

    def merge2Lists(self, l1, l2):
        head = point = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next
            else:
                point.next = l2
                l2 = l1
                l1 = point.next.next
            point = point.next
        if not l1:
            point.next=l2
        else:
            point.next=l1
        return head.next

Java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.Comparator;
import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    ListNode(Integer[] nums) {
        ListNode currNode = this;
        currNode.val = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currNode.next = new ListNode(nums[i]);
            currNode = currNode.next;
        }
    }

    @Override
    public String toString() {
        ListNode currNode = this;
        StringBuilder s = new StringBuilder();
        while (currNode != null) {
            s.append(currNode.val);
            s.append(" -> ");
            currNode = currNode.next;
        }
        // 最后添加一个 NULL 标志表示添加到末尾了
        s.append("NULL");
        return s.toString();
    }
}

public class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        return mergeKLists(lists, 0, len - 1);
    }

    public ListNode mergeKLists(ListNode[] lists, int l, int r) {
        // 思考这里为什么取等于？这是因为根据下文对 mergeKLists 的递归调用情况，区间最窄的时候，只可能是左右端点重合
        if (l == r) {
            return lists[l];
        }
        int mid = (r - l) / 2 + l;
        ListNode l1 = mergeKLists(lists, l, mid);
        ListNode l2 = mergeKLists(lists, mid + 1, r);
        return mergeTwoSortedListNode(l1, l2);
    }

    private ListNode mergeTwoSortedListNode(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoSortedListNode(l1.next, l2);
            return l1;
        }
        l2.next = mergeTwoSortedListNode(l1, l2.next);
        return l2;
    }
}

复杂度分析

  • 时间复杂度：O(Nlogk) ，其中 k 是链表的数目。

    • 我们可以在 O(n) 的时间内合并两个有序链表，其中 n 是两个链表中的总节点数。
    • 将所有的合并进程加起来，我们可以得到：O(Nlogk) 。
  • 空间复杂度：O(1)
    • 我们可以用 O(1)的空间实现两个有序链表的合并。