Java有序鏈表的合并實(shí)現(xiàn)方法

更新時(shí)間：2023年04月13日 10:06:51 作者：ziop-三月

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

問題

將兩個(gè)升序鏈表合并為一個(gè)新的升序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例 1：

輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]

示例二：

<strong>輸入：</strong>l1 = [], l2 = []
<strong>輸出：</strong>[]

示例 3：

輸入：l1 = [], l2 = [0]
輸出：[0]

思路

版本一

新建一個(gè)空的鏈表 nList
在兩個(gè)鏈表（l1,l2）都不為空的情況下，比較兩個(gè)鏈表的第一個(gè)元素的值的大小，取出最小的加入到新鏈表當(dāng)中，然后小鏈表的頭指針指向下一位，并且nList的指針也指向下一位
如果兩個(gè)鏈表還都不為空，繼續(xù)循環(huán)
如果兩個(gè)鏈表有一個(gè)為空，那么將不為空的鏈表拼接到nList后邊
最后返回 nList 的next 作為新鏈表的頭結(jié)點(diǎn)

版本二

首先判斷兩個(gè)鏈表是否為空，為空直接返回空鏈表。不為空的繼續(xù)向下走
判斷 l1 和 l2的頭結(jié)點(diǎn)誰更小，則將這個(gè)節(jié)點(diǎn)保存為頭結(jié)點(diǎn)，后邊的節(jié)點(diǎn)一次拼接在該節(jié)點(diǎn)上邊。
后邊思路同版本一

答案

版本一

新建一個(gè)節(jié)點(diǎn)，將原來的鏈表都傳到新的鏈表當(dāng)中

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode   = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        all.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        all = all.next;
    }
    all.next = list1 != null ? list1 : list2;
    return head.next;
}

版本二

從原來的鏈表中選擇出來一個(gè)進(jìn)行整合，不適用任何新的內(nèi)存

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null || list2 == null) {
        return list1 == null ? list2 : list1;
    }
    ListNode head = list1.val <= list2.val ? list1 : list2;
    if (list1.val <= list2.val)
        list1 = list1.next;
    else
        list2 = list2.next;
    ListNode tmp = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        tmp.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        tmp = tmp.next;
    }
    tmp.next = list1 != null ? list1 : list2;
    return head;
}

到此這篇關(guān)于Java有序鏈表的合并實(shí)現(xiàn)方法的文章就介紹到這了,更多相關(guān)Java有序鏈表合并內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: