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]

Example 2

Input: list1 = [], list2 = []
Output: []

Example 3

Input: list1 = [], list2 = [0]
Output: [0]

Explanation

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

Solution

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

鏈結串列比較難解釋，首先要先知道鏈結串列的特性，它是屬於動態記憶體配置，為了返回指標在第一個節點的鏈結串列，我建立兩個鏈結串列分別為 res 和 cur ，res 是最終要返回的值，而 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;
}

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 ⭐ I'd appreciate it.