題目

輸入k個排序的鏈表，請將它們合并成一個排序的鏈表。

分析：利用最小堆選取值最小的節(jié)點

用k個指針分別指向這k個鏈表的頭節(jié)點，每次從這k個節(jié)點中選取值最小的節(jié)點。然后將指向值最小的節(jié)點的指針向后移動一步，再比較k個指針指向的節(jié)點并選取值最小的節(jié)點。重復(fù)這個過程，直到所有節(jié)點都被選取出來。

解

public class Test {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        ListNode listNode7 = new ListNode(7);
        ListNode listNode8 = new ListNode(8);
        ListNode listNode9 = new ListNode(9);

        listNode1.next = listNode4;
        listNode4.next = listNode7;

        listNode2.next = listNode5;
        listNode5.next = listNode8;

        listNode3.next = listNode6;
        listNode6.next = listNode9;

        ListNode[] lists = {listNode1, listNode2, listNode3};
        ListNode result = mergeKLists(lists);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }

        while (!minHeap.isEmpty()) {
            ListNode least = minHeap.poll();
            cur.next = least;
            cur = least;

            if (least.next != null) {
                minHeap.offer(least.next);
            }
        }

        return dummy.next;
    }
}

分析：按照歸并排序的思路合并鏈表

輸入的k個排序鏈表可以分成兩部分，前k/2個鏈表和后k/2個鏈表。如果將前k/2個鏈表和后k/2個鏈表分別合并成兩個排序的鏈表，再將兩個排序的鏈表合并，那么所有鏈表都合并了。合并k/2個鏈表與合并k個鏈表是同一個問題，可以調(diào)用遞歸函數(shù)解決。文章來源地址http://www.zghlxwxcb.cn/news/detail-772842.html

解

public class Test {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        ListNode listNode7 = new ListNode(7);
        ListNode listNode8 = new ListNode(8);
        ListNode listNode9 = new ListNode(9);

        listNode1.next = listNode4;
        listNode4.next = listNode7;

        listNode2.next = listNode5;
        listNode5.next = listNode8;

        listNode3.next = listNode6;
        listNode6.next = listNode9;

        ListNode[] lists = {listNode1, listNode2, listNode3};
        ListNode result = mergeKLists(lists);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        return mergeLists(lists, 0, lists.length);
    }

    private static ListNode mergeLists(ListNode[] lists, int start, int end) {
        if (start + 1 == end) {
            return lists[start];
        }

        int mid = (start + end) / 2;
        ListNode head1 = mergeLists(lists, start, mid);
        ListNode head2 = mergeLists(lists, mid, end);
        return merge(head1, head2);
    }

    private static ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
            }
            else {
                cur.next = head2;
                head2 = head2.next;
            }

            cur = cur.next;
        }
        cur.next = head1 == null ? head2 : head1;
        return dummy.next;
    }
}

到了這里，關(guān)于面試算法78：合并排序鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！