首頁 >Java >java教程 >Java有序鍊錶怎麼合併

Java有序鍊錶怎麼合併

PHPz
PHPz轉載
2023-04-19 20:43:051623瀏覽

問題

將兩個升序鍊錶合併為一個新的升序鍊錶並傳回。新鍊錶是透過拼接給定的兩個鍊錶的所有節點組成的。

範例1:

Java有序鍊錶怎麼合併

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

範例二:

8e99a69fbe029cd4e2b854e244eab143輸入:128dba7a3a77be0113eb0bea6ea0a5d0l1 = [], l2 = []
8e99a69fbe029cd4e2b854e244eab143輸出:128dba7a3a77be0113eb0bea6ea0a5d0[]

##範例3:

輸入:l1 = [] , l2 = [0]

輸出:[0]

想法

#版本一

  • 新建一個空的鍊錶nList

  • 在兩個鍊錶(l1,l2)都不為空的情況下,比較兩個鍊錶的第一個元素的值的大小,取出最小的加入到新鍊錶當中,然後小鍊錶的頭指標指向下一位,而nList的指標也指向下一位

  • 如果兩個鍊錶還都不為空,繼續循環

  • 如果兩個鍊錶有一個為空,那麼將不為空的鍊錶拼接到nList後邊

  • 最後一個回傳nList 的next 作為新鍊錶的頭結點

版本二

  • 先判斷兩個鍊錶是否為空,為空直接回傳空鍊錶。不為空的繼續向下走

  • 判斷l1 和l2的頭結點誰更小,則將這個節點保存為頭結點,後邊的節點一次拼接在該節點上邊。

  • 後邊思路同版本一

答案

版本一

新節點,將原來的鍊錶都傳到新的鍊錶當中

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;
}

版本二

從原來的鍊錶中選擇出來一個進行整合,不適用任何新的記憶體

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;
}

以上是Java有序鍊錶怎麼合併的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:yisu.com。如有侵權,請聯絡admin@php.cn刪除