DEV Community

Cover image for Merge Two Sorted Lists
FakeStandard
FakeStandard

Posted on

Merge Two Sorted Lists

#21.Merge Two Sorted Lists

Problem statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: list1 = [], list2 = []
Output: []
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: list1 = [], list2 = [0]
Output: [0]
Enter fullscreen mode Exit fullscreen mode

Explanation

給定兩個已排序的 Linked List,分別為 l1l2 ,將兩個 Linked List 合併成一個 Linked List,並且該鏈結串列必須通過兩個鏈結串列的節點拼湊在一起,返回一個同樣排序的鏈結串列,返回的鏈結串列必須是第一個節點

Solution

一開始先判斷兩個鏈結串列是否為 null,如果有一個是 null,則直接返回另一個鏈結串列

鏈結串列比較難解釋,首先要先知道鏈結串列的特性,它是屬於動態記憶體配置,為了返回指標在第一個節點的鏈結串列,我建立兩個鏈結串列分別為 rescurres 是最終要返回的值,而 cur 是用來合併時使用的,並且讓 cur = res ,當 cur 被變更時,res 也會有相同的變化,因為指標欄是指向同一塊記憶體位置

使用 while 執行兩個鏈結串列當前值的比較,值比較小的就將當下的節點指給 cur.next ,並將其移動到下一個指標記錄的記憶體位置,最後將 cur 移動到下一個指標記錄的記憶體位置,以繼續連結接下來的比較結果節點,直到任一鏈結串列為 null 時就結束迴圈作業,最後將剩餘未進行比較的節點連結到 cur 的下一個指標欄,然後合併結果 res.next

public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
    if (l1 == null || l2 == null) return l1 ?? l2;

    ListNode res = new ListNode(), cur = res;

    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 ?? l2;

    return res.next;
}
Enter fullscreen mode Exit fullscreen mode

Reference

LeetCode Solution

GitHub Repository


Thanks for reading the article 🌷 🌻 🌼

If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub
or buy me a coffee ⬇️ I'd appreciate it.

Buy-me-a-coffee


Top comments (0)