【LeetCode】23.合并K个排序链表

题目描述

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

示例：

输入:

[

  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)

巴特西

【LeetCode】23.合并K个排序链表

题目描述

题目解析

方法一：暴力法

方法二：堆排序法

方法三：分治法

最新文章

热门文章