淘先锋技术网

首页 1 2 3 4 5 6 7

请添加图片描述

文章目录

题目

合并 K 个升序链表

难度: 困难

描述:

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

提示:

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

思路

时间复杂度分析:因为允许k的长度为10^4,所以O(n2)是肯定过不去的,可以使用O(nlogn)或者更低,提示中标红处是我们需要注意的地方
解法思路:本题我使用的是暴力解法,首先先将这个链表集合中的所有元素进行合并,生成一个长的链表,因为子链表的长度在500范围内,所以时间复杂度最终会是O(n),同时使用快速排序进行排序,最终时间复杂度在O(nlogn)

代码

先将链表集合中的所有子链表合成一条链表:

 public static ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        for(int  i =0;i<k;i++){
            while(lists[i] != null){
                ListNode temp = lists[i];
                lists[i] = lists[i].next;
                tail.next= temp;
                tail = tail.next;
            }
        }
        return quickSort(dummy.next);
    }

然后对链表进行快速排序:
快速排序思路:设置一个中间值,将小于该值的数放在左边,大于的放在右边
针对本题:设置三个链表,一个存储小于的值,一个存储等于的值,一个存储大于的值

public static  ListNode quickSort(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode pivot = head;
        ListNode lessHead = new ListNode(-1);
        ListNode lessTail = lessHead;
        ListNode biggerHead = new ListNode(-1);
        ListNode biggerTail = biggerHead;
        ListNode equalHead = new ListNode(-1);
        ListNode equalTail = equalHead;

        ListNode current = head;
        while(current != null){
            if(current.val < pivot.val){
                lessTail.next = current;
                lessTail=lessTail.next;
            }else if(current.val > pivot.val){
                biggerTail.next = current;
                biggerTail = biggerTail.next;
            }else{
                equalTail.next = current;
                equalTail = equalTail.next; 
            }
            current = current.next;
        }
        lessTail.next =null;
        biggerTail.next =null;
        equalTail.next = null;
        
        ListNode sortedLess = quickSort(lessHead.next);
        ListNode sortedBigger = quickSort(biggerHead.next);
        return concer(sortedLess,equalHead.next,sortedBigger);
    }

然后分别从小到大,依此添加到链表中:

 public static ListNode concer(ListNode less,ListNode euqal,ListNode bigger){
        ListNode dummyhead = new ListNode(-1);
        ListNode tail = dummyhead;

        tail.next = less;
        tail = getTail(tail);
        tail.next =euqal ;
        tail = getTail(tail);
        tail.next = bigger;
    

        return dummyhead.next;
    }
    public static ListNode getTail(ListNode head){
        if(head == null){
            return null;
        }
        while(head.next != null){
            head = head.next;
        }
        return head;
    }

我这里使用了最简单的方法,还有很多优质的解法,可以参考力扣中大神的做法。

完整代码:

/**
 * 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 static ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        for(int  i =0;i<k;i++){
            while(lists[i] != null){
                ListNode temp = lists[i];
                lists[i] = lists[i].next;
                tail.next= temp;
                tail = tail.next;
            }
        }
        return quickSort(dummy.next);
    }
    public static  ListNode quickSort(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode pivot = head;
        ListNode lessHead = new ListNode(-1);
        ListNode lessTail = lessHead;
        ListNode biggerHead = new ListNode(-1);
        ListNode biggerTail = biggerHead;
        ListNode equalHead = new ListNode(-1);
        ListNode equalTail = equalHead;

        ListNode current = head;
        while(current != null){
            if(current.val < pivot.val){
                lessTail.next = current;
                lessTail=lessTail.next;
            }else if(current.val > pivot.val){
                biggerTail.next = current;
                biggerTail = biggerTail.next;
            }else{
                equalTail.next = current;
                equalTail = equalTail.next; 
            }
            current = current.next;
        }
        lessTail.next =null;
        biggerTail.next =null;
        equalTail.next = null;
        
        ListNode sortedLess = quickSort(lessHead.next);
        ListNode sortedBigger = quickSort(biggerHead.next);
        return concer(sortedLess,equalHead.next,sortedBigger);
    }
    public static ListNode concer(ListNode less,ListNode euqal,ListNode bigger){
        ListNode dummyhead = new ListNode(-1);
        ListNode tail = dummyhead;

        tail.next = less;
        tail = getTail(tail);
        tail.next =euqal ;
        tail = getTail(tail);
        tail.next = bigger;
    

        return dummyhead.next;
    }
    public static ListNode getTail(ListNode head){
        if(head == null){
            return null;
        }
        while(head.next != null){
            head = head.next;
        }
        return head;
    }
}