Java合并兩個及以上有序鏈表的示例詳解

更新時間：2022年11月24日 10:53:01 作者：Grey

這篇文章主要通過兩個例題為大家介紹一下Java合并兩個及以上有序鏈表的實現(xiàn)方法，文中的示例代碼講解詳細，具有一定的學習價值，需要的可以參考一下

題目一：合并兩個有序鏈表

題目鏈接

題目一思路

設置兩個指針，一個指針（t1）指向l1鏈表頭，另外一個指針（t2）指向l2鏈表頭。

首先判斷l(xiāng)1和l2的第一個元素，誰小，誰就是最后要返回的鏈表的頭節(jié)點，如果l1和l2的第一個元素相等，隨便取哪個都可以。

這樣，我們就設置好了要返回鏈表的頭節(jié)點，假設頭節(jié)點是head，

依次移動t1和t2指針，誰小，誰就接入進來。依次操作，直到兩個鏈表都遍歷完畢為止。

此外，有個顯而易見的結論：如果l1和l2有一個鏈表為空，則返回那個不為空的鏈表即可

題目一完整代碼

public class LeetCode_0021_MergeTwoSortedLists {

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            // 如果任何一個鏈表為空，那么直接返回另外一個鏈表即可
            return l1 == null ? l2 : l1;
        }
        // 誰小誰作為頭
        ListNode head = l1.val > l2.val ? l2 : l1;
        // t1 和 t2 表示l1和l2下一個要遍歷的位置
        ListNode t1 = head == l1 ? l1.next : l1;
        ListNode t2 = head == l2 ? l2.next : l2;
        ListNode cur = head;
        while (t1 != null || t2 != null) {
            if (t1 == null) {
                // l1鏈表已經(jīng)到頭，剩下只需要把l2鏈表接入進來即可
                cur.next = t2;
                t2 = t2.next;
                cur = cur.next;
                continue;
            }
            if (t2 == null) {
                // l2鏈表已經(jīng)到頭，剩下只需要把l2鏈表接入進來即可
                cur.next = t1;
                t1 = t1.next;
                cur = cur.next;
                continue;
            }
            // l1和l2都沒有到頭，那么誰小誰接入進來即可。
            if (t1.val > t2.val) {
                cur.next = t2;
                t2 = t2.next;
            } else {
                cur.next = t1;
                t1 = t1.next;
            }
            cur = cur.next;
        }
        return head;
    }
}

題目二：合并多個有序鏈表

23. Merge k Sorted Lists

題目二關鍵思路

準備一個小根堆，并把每個鏈表的頭節(jié)點加入到小根堆中，此時，小根堆堆頂彈出的節(jié)點一定是最后生成鏈表的頭節(jié)點。

假設鏈表為：L1,L2...LN

第一步，先將L1,L2...LN的頭節(jié)點L1H,L2H...LNH加入小根堆

第二步，從小根堆堆頂彈出一個元素，作為最后鏈表的頭節(jié)點。

第三步，第二步中彈出節(jié)點所在的鏈表假設是i號鏈表，那么就找彈出節(jié)點的下一個位置（假設為X）再和小根堆堆頂元素比較：

如果X比堆頂元素大，則堆頂元素彈出，X進入小根堆

如果X比堆頂元素小，則直接不需要進入堆頂，作為結果鏈表

題目二完整代碼

public class LeetCode_0023_MergeKSortedLists {

    public static class ListNode {
        int val;
        ListNode next;
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (null == lists || lists.length == 0) {
            return null;
        }
        if (1 == lists.length) {
            return lists[0];
        }
        // 小根堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        for (ListNode list : lists) {
            if (null != list) {
                queue.add(list);
            }
        }
        ListNode res = queue.poll();
        ListNode head = res;
        while (!queue.isEmpty()) {
            if (res != null) {
                ListNode n = res.next;
                if (n == null) {
                    res.next = queue.poll();
                    res = res.next;
                } else if (n.val > queue.peek().val) {
                    res.next = queue.poll();
                    res = res.next;
                    queue.add(n);
                } else {
                    res = res.next;
                }
            }
        }
        return head;
    }
}

到此這篇關于Java合并兩個及以上有序鏈表的示例詳解的文章就介紹到這了,更多相關Java合并有序鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: