合并K个有序链表合并K个有序链表

68 阅读 0 评论 45 点赞

我是靠谱客的博主彩色航空，最近开发中收集的这篇文章主要介绍合并K个有序链表合并K个有序链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

合并K个有序链表

题目描述：给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
方法一初始化ans = null，遍历每个链表，与ans合并，更新ans为合并后的链表。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for(ListNode node: lists){
            ans = mergeTwoLists(ans, node);
        }
        return ans;

    }

    public ListNode mergeTwoLists(ListNode ans, ListNode l){
        if(ans == null) return l;
        if(l == null) return ans;
        ListNode head = new ListNode(0);
        ListNode l1 = ans, l2 = l, cur = head;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1: l2;
        return head.next;
    }
}

方法二定义一个新的类，实现Comparable接口，重写compareTo方法。将K个新的链表节点放入优先队列中，每次取队头结点时，放入原链表头结点的下一个结点。

class Solution {
    class CompaerNode implements Comparable<CompaerNode>{
        int val;
        ListNode node;

        CompaerNode(int val, ListNode node){
            this.val = val;
            this.node = node;
        }

        public int compareTo(CompaerNode other){
            return this.val - other.val;
        }
    }

    PriorityQueue<CompaerNode> que = new PriorityQueue<>();
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = new ListNode(0);
        ListNode cur = ans;
        for(ListNode list: lists){
            if(list != null)
                que.offer(new CompaerNode(list.val, list));
        }

        while(!que.isEmpty()){
            CompaerNode firstNode = que.poll();
            cur.next = firstNode.node;
            cur = cur.next;
            if(firstNode.node.next != null){
                que.offer(new CompaerNode(firstNode.node.next.val, firstNode.node.next));
            }
        }
        return ans.next;
    }   
}

方法三归并排序，先分割，在两两合并

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

    public ListNode merge(ListNode[] lists, int l, int r){
        if (l == r) {
            return lists[l]; // l==r时，相当于一个非空链表与一个null合并
        } else if (l > r) {
            return null;
        } else {
            int mid = ((r - l) >> 1) + l;
            return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
        }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return (l1 != null) ? l1 : l2;
        }
        ListNode ret = new ListNode(-1);
        ListNode cur = ret;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        cur.next = (l1 != null) ? l1 : l2;
        return ret.next;
    }
}