題目:
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into 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.
給定兩個已排序鍊錶的頭list1和list2。
將兩個清單合併為一個排序清單。此清單應由前兩個清單的節點拼接而成。
傳回合併後的鍊錶的頭。
題目說明
給定兩個 遞增排序的單向鏈表 list1 和 list2,把它們合併成一個新的遞增排序鏈表,並回傳這個鏈表的頭節點。
解題思路
這題的核心就是 兩個有序鏈表的歸併,類似「歸併排序」的合併步驟。
虛擬頭節點 (dummy node)
建立一個 dummy,讓結果鏈表從 dummy.next 開始,簡化邊界處理。
兩個指標
指向 list1、list2 的頭節點,逐一比較。
把小的節點接到新鏈表上,並移動對應指標。
處理剩餘部分
當其中一個鏈表為空時,把另一個鏈表整段接上去即可。