切換
舊版
前往
大廳
主題

LeetCode - 21. Merge Two Sorted Lists 解題心得

Not In My Back Yard | 2020-07-29 00:01:19 | 巴幣 2 | 人氣 314

題目連結:


題目意譯:
合併兩個已排序之連結串列(Linked List)l1 、 l2 並回傳一個新的已排序串列。新的串列應當由兩個串列之節點拼接在一起而形成。



範例測資:
範例:
輸入: 1->2->4, 1->3->4
輸出: 1->1->2->3->4->4


解題思維:
如果有寫過合併排序(Merge Sort),則這題概念應該不陌生。

看哪個串列的第一個數字較小,就取該位置當作合併後的頭。接著,將以兩個指標 p1 、 p2 各自指向兩個串列目前正要看的元素。

如果 p1 指到的元素值較小,代表其值應接在新的串列之尾端(用另一個指標指向新串列的尾端元素,其後的元素就是接在該尾端的後面,形成新的尾端),然後將 p1 指到對應的下一個元素;若 p2 較小,則同理;若兩者一樣大,則隨便取一者加進去。

重複以上步驟直到 p1 或 p2 為空指標(沒有新的元素了),則將非空指標的該指標指到的元素全數接在新串列之後方。最後的新串列即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作