#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
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.
Top comments (0)