DAY 5
6
Software Development

[Day 5] 從LeetCode學演算法 - 0021. Merge Two Sorted Lists (Easy)

``````Question:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
``````
``````Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
``````

(在C/C++裡面連結基本上就是指標(pointer))

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
``````

val用來存放每個node的值，next用來指向到下一個node

``````ListNode b = a.next; // 因為一開始我們只知道a的位置而已XD
ListNode c = new ListNode(20);
b.next = c;
``````

(會依照各自編譯器的規範，只是以我們而言是真的就沒辦法找到它了)

``````// a -> c -> b
ListNode b = a.next;
ListNode c = new ListNode(20);
a.next = c;
c.next = b;
``````

(遞迴的概念，我們之後再專門做一篇相關的來講解)

l1是全空的狀況下，那其實答案就是l2(因為後面就不用繼續排了)，

l1: 1 -> 3 -> 5 ->8 ->10, l2: 2 -> 4 -> 4
1先跟2比，1比較小所以當頭(1) ->
3跟2比，2比較小(1->2) ->
3跟4比(1->2->3) ->
5跟4比(1->2->3->4) ->
5跟4比(1->2->3->4->4) ->
l2的部分已經空了，填入l1中5以後剩下的部分
(1->2->3->4->4-> 5 ->8 ->10)

Java:

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}

``````

prevnext會指定給下一個比較過後較小的那個節點

l1或l2(看哪個比較小)就自己遞移到下一個節點

Python:

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dum = ListNode(None)
prev = dum

while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next

if l1 == None:
prev.next = l2
elif l2 == None:
prev.next = l1

return dum.next

``````

「請用iterative(迭代或迴圈)/recursive(遞迴)的方式來解」
(上面Java是recursive solution，Python是iterative solution，

「使用遞迴的話會有什麼限制？」
(有可能受到編譯器規範的最大function stack上限限制，

「那為什麼你會用遞迴？」
(因為遞迴比較好想啊XDDDDD)(別這麼誠實，雖然大家都知道XD)
(因為在一般狀況下，遞迴解通常會較為容易閱讀，

「時間複雜度是？」
( worst case是O(N1+N2)，best case是O(min(N1, N2))。)

(這樣會比較簡單，一樣兩兩比較，

0026. Remove Duplicates from Sorted Array (Easy)

1 則留言

2
hyj1116
iT邦新手 4 級 ‧ 2019-10-03 23:03:19

// a -> c -> b
ListNode b = a.next;
ListNode c = new ListNode(20);
a.next = c;
c.next = b;

// a -> c -> b
ListNode b = a.next;
ListNode c = new ListNode(20);
c.next = b;
a.next = c;

Desolve iT邦新手 5 級 ‧ 2019-10-04 00:34:20 檢舉

``````>>> class ListNode:
...   def __init__(self, x):
...     self.val = x
...     self.next = None
...
>>> a = ListNode(1)
>>> a.next = ListNode(3)
>>> b = a.next
>>> c = ListNode(20)
>>> a
<__main__.ListNode object at 0x0000000002838DA0>
>>> a, a.val
(<__main__.ListNode object at 0x0000000002838DA0>, 1)
>>> a.next, a.next.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>> b, b.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>> c, c.val
(<__main__.ListNode object at 0x0000000002838B70>, 20)
>>>
>>> a.next = c
>>> c.next = b
>>> b, b.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>> c, c.val
(<__main__.ListNode object at 0x0000000002838B70>, 20)
>>> a.next, a.next.val
(<__main__.ListNode object at 0x0000000002838B70>, 20)
>>> c.next, c.next.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>>

``````

「將a.next的記憶體位址設定為c的記憶體位址」

``````a = ListNode(1)
a.next = ListNode(3) # 也就是b，但我們沒有宣告b來存
c = ListNode(20)
a.next = c # 將a的next指向到c的記憶體位址
# 這時候因為沒有人存ListNode(3)，所以它就再也存取不到了！
``````