题目描述

23.合并K个排序链表

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

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。
示例:
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

题目解析

方法一:暴力法

解题思路

合并K个排序链表,首先我们直接采用暴力法去解决,将链表所有节点的val值放入一个List中,然后将这个List进行排序,根据排序后的List重新构建新链表。

代码示例

Java:

/**
 * Definition for singly-linked list.
 */
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { 
        val = x;
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // 1. 将链表节点放入一个List中
        List<Integer> arr = new ArrayList<Integer>();
        for (int i = 0; i < lists.length; i++) {
            ListNode cur = lists[i];
            while(cur != null) {
                arr.add(cur.val);
                cur = cur.next;
            }
        }

        // 2. 排序
        Collections.sort(arr);
        
        // 3. 重新构建链表
        ListNode res = new ListNode(0);
        ListNode cur = res;
        for(int i = 0; i < arr.size(); i++) {
            ListNode node = new ListNode(arr.get(i));
            cur.next = node;
            cur = cur.next;
        }
        return res.next;
    }
}

复杂度分析

时间复杂度:O(N * log(N)), N代表所有链表节点数量。

  • 遍历所有值需要花费O(N)时间
  • 稳定的排序算法花费N * log(N)时间
  • 重新构建链表需要花N * log(N)时间

空间复杂度:O(N)

方法二:堆排序法

解题思路

采用堆的方式来进行链表节点的排序,创建一个大小为K的小根堆,首先将K个链表的头指针插入到堆中,然后取出堆顶元素,同时将堆顶元素的下一个节点插入到最小堆中,然后循环该操作直至链表节点全部遍历完成。

代码示例

Java:

/**
 * Definition for singly-linked list.
 */
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { 
        val = x;
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // 1. 初始化小根堆
        PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() {
    			public int compare(ListNode o1, ListNode o2) {
    				return (o1.val - o2.val);
    			}
    		});
        for(int i = 0; i < lists.length; i++) {
            if (lists[i] != null) queue.add(lists[i]);
        }

        // 2. 取出堆顶元素,并将堆顶元素的下一节点插入小根堆
        ListNode res = new ListNode(0);
        ListNode cur = res;
        while(!queue.isEmpty()) {
            ListNode top = queue.poll();
            if (top.next != null) {
                queue.add(top.next);
            }
            cur.next = top;
            cur = cur.next;
        }
        return res.next;
    }
}

复杂度分析

时间复杂度:O(N * log(K)),N代表所有链表节点数量,K代表链表的个数。

空间复杂度:O(K)

方法三:分治法

解题思路

我们将K个链表对半划分,先合并前K/2个链表,再合并后K/2个链表,然后将前K/2个链表合并成的链表再与后K/2个链表合并的链表进行合并,得到最终结果。

在处理前K/2个和后K/2个链表时,就跟上述方法思路一致,通过递归的方式不停的将链表进行划分,直到链表无法继续划分为止,将链表返回给递归的上一层进行两两合并。

分治思路:划分子问题 --> 合并子问题结果【递归实现】

代码示例

Java:

/**
 * Definition for singly-linked list.
 */
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { 
        val = x;
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return divide(lists, 0, lists.length-1);
    }

    public ListNode divide(ListNode[] lists, int lo, int hi) {
        if (lo == hi) return lists[lo];
        int mid = lo + (hi - lo) / 2;
        ListNode left = divide(lists, lo, mid);
        ListNode right = divide(lists, mid + 1, hi);
        return merge(left, right);
    }

    public ListNode merge(ListNode l1, ListNode l2) {
		if(l1 == null || l2 == null) {
			return (l1 == null) ? l2 : l1;
		}
		if(l1.val <= l2.val) {
			l1.next = merge(l1.next,l2);
			return l1;
		} else {
			l2.next = merge(l1, l2.next);
			return l2;
		}
	}
}

复杂度分析

时间复杂度:O(N * log(K)),N代表所有链表节点数量,K代表链表的个数。

空间复杂度:O(K)

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄