Linked list Pyhton - LeetCode

  Delete Node in a Linked List

class Solution: def deleteNode(self, node): """ :type node: ListNode :rtype: void Do not return anything, modify node in-place instead. Input: head = [4,5,1,9], node = 5 Output: [4,1,9] """ node.val=node.next.val node.next=node.next.next

Remove Nth Node From End of List

class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy=ListNode(0) dummy.next=head slow = fast = dummy for i in range(n): fast=fast.next while fast and fast.next: fast=fast.next slow=slow.next slow.next=slow.next.next return dummy.next

class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: # Step 1: Define dummy node to handle edge case of removing head dummy = ListNode(0) dummy.next = head fast = slow = dummy # Step 2: Move fast pointer n+1 steps ahead for _ in range(n + 1): fast = fast.next print(fast) # Step 3: Move both pointers until fast pointer reaches the end while fast != None: fast = fast.next slow = slow.next # Step 4: Remove the nth node from the end slow.next = slow.next.next return dummy.next

 

1

  Reverse Linked List

class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: prev = None #因為要反轉 + list的最後一個值一定是None while head: next1 = head.next #[1,2,3,4,5] [2,3,4,5] [3,4,5] head.next = prev # [1,none] [2,1,none] [3,2,1,none] prev = head #[1,none] [2,1,none] [3,2,1,none] head = next1 #[2,3,4,5] [3,4,5] [4,5] return prev;

  Merge Two Sorted Lists

class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy=ListNode(0) current=dummy while list1 and list2: if list1.val>=list2.val: current.next=list2 current=current.next list2=list2.next else: current.next=list1 current=current.next list1=list1.next if list1: current.next=list1 elif list2: current.next=list2 return dummy.next

class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: # Create a dummy node as the starting point of merged list dummy_head = ListNode(0) current = dummy_head p1, p2 = list1, list2 # Traverse both lists and merge while p1 and p2: if p1.val <= p2.val: current.next = p1 p1 = p1.next else: current.next = p2 p2 = p2.next current = current.next # Attach the remaining nodes of list1 or list2 if p1: current.next = p1 elif p2: current.next = p2 # Return the merged list, skipping the dummy head return dummy_head.next

在這段程式碼中，我們使用了 dummy_head 這個虛擬的節點作為合併後鏈表的起始點。這樣做的原因是為了簡化鏈表操作，特別是在開始時和結束時的處理：

1. 虛擬節點 dummy_head 的用途：

   • dummy_head 是一個空的節點，其 next 指向真正的合併後的鏈表的頭部。這樣一來，在建構鏈表的過程中，我們可以直接操作 dummy_head.next 而不用單獨處理頭部節點的特殊情況。

2. 為何返回 dummy_head.next 而不是 current？：

   • 當我們完成遍歷並合併兩個鏈表後，current 已經指向了合併後鏈表的最後一個節點。然而，由於 current 在遍歷過程中一直在移動，最終會指向 None。
   • 因此，直接返回 current 是不合適的，因為它是 None，而不是合併後的鏈表的頭部節點。
   • 反之，dummy_head.next 始終指向合併後的鏈表的頭部，即使 dummy_head 是一個虛擬節點，但其 next 指向的節點是我們要返回的合併後鏈表的頭部。

因此，為了返回正確的結果，我們應該返回 dummy_head.next，而不是 current。這樣做可以確保我們返回的是合併後鏈表的正確頭部節點，同時也符合我們在開始時使用 dummy_head 的設計思路。

current = dummy_head 這行程式碼確實是將指針 current 設置為指向 dummy_head 的意思。

1. current 的初始化：

   • 當我們寫 current = dummy_head 時，我們實際上是將 current 這個指針指向了 dummy_head。這樣做是非常有用的，因為在之後的遍歷過程中，我們可以使用 current 來迭代並建構合併後的鏈表。
   • 最初的 dummy_head 是一個空節點，而 current 則是用來追踪我們合併後鏈表的最後一個節點。

2. 為何這樣可以設置成功？：

   • 在 Python 中，對象的指針賦值是基於參考的。當我們寫 current = dummy_head 時，current 實際上指向了 dummy_head 在記憶體中的位置。
   • 因此，當我們後續對 current 進行操作時，例如 current.next = some_node，這個操作也會同時影響到 dummy_head，因為它們實際上是指向同一個物件的不同名稱。
   • 這種設計方式讓我們可以更加方便地管理鏈表，特別是在需要進行頭部插入或者在開始處理前沒有有效節點的情況下。

總結來說，current = dummy_head 的設置是為了方便我們在合併兩個鏈表的過程中操作，而不必擔心初始條件的複雜性。

解法解析

1. 初始化

   • 首先，我們建立一個新的空節點 dummy_head 作為合併後鏈表的起始點。然後再設置一個指針 current 指向 dummy_head，用來遍歷並構建合併後的鏈表。

2. 合併過程

   • 我們使用兩個指針 p1 和 p2 分別指向兩個待合併鏈表的頭部 list1 和 list2。
   • 逐一比較 p1 和 p2 指向節點的值，將值較小的節點接到 current.next，並將 current 往後移動一位 (current = current.next)。
   • 當其中一個鏈表遍歷完畢後，將剩餘未遍歷完的鏈表部分直接接到 current.next。

3. 結束

• 最後返回 dummy_head.next 即可，這是因為 dummy_head 是一個空節點，真正的合併後鏈表的頭部是從 dummy_head.next 開始的。

  Palindrome Linked List

當A每次走兩步，B每次走一步，A走到末尾時，B大概就是A所走過的一半路程。

class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: record=[] while head: record.append(head.val) head=head.next for i in range(len(record)//2): if record[i]!=record[-1-i]: return False return True

class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: fast = slow = head while fast and fast.next: fast=fast.next.next slow=slow.next pre=None while slow: next1=slow.next slow.next=pre pre=slow slow=next1 first_half = head second_half = pre while second_half: if first_half.val != second_half.val: return False first_half = first_half.next second_half = second_half.next return True

這個問題涉及到遍歷鏈表時，使用 fast 和 slow 雙指針來找到鏈表中點的技巧。讓我們來理解為什麼在 while fast and fast.next: 可行而 while fast.next: 會導致錯誤。

使用 while fast and fast.next: 的原因：

在判斷是否為迴文時，我們需要找到鏈表的中點，這可以通過一個快指針 fast 和一個慢指針 slow 同時遍歷來實現。這裡的目標是確保 fast 和 fast.next 都存在，以便在迭代時不會遇到 NoneType 的錯誤。

• fast 每次移動兩步，slow 每次移動一步，這樣當 fast 達到鏈表尾部時，slow 正好指向鏈表的中間節點（對於偶數長度的鏈表來說，是靠右側的中點）或者中間兩個節點的第一個。

• 因此，while fast and fast.next: 的條件確保了在每次迭代中，fast 都不是 None 並且 fast.next 也不是 None，這樣就能安全地進行 fast.next.next 和 slow.next 的訪問。

為何 while fast.next: 不可行：

如果使用 while fast.next: 作為條件來遍歷，這意味著在 fast 是最後一個節點時，還會嘗試訪問 fast.next。這樣的話，在 fast 為最後一個節點時，fast.next 是 None，因此當遍歷到最後一個節點時，這條件會導致異常，因為 None 沒有 next 屬性。

解決方案的實現思路：

1. 使用 fast 和 slow 找到中點。
2. 將鏈表的後半部分反轉。
3. 逐步比較前半部分和反轉後的後半部分來確定是否為迴文。

這樣的設計保證了在 O(n) 的時間內完成，並且只使用了 O(1) 的額外空間（用於指針變量）來達到判斷迴文的目的。

https://ithelp.ithome.com.tw/articles/10285898

快慢指針來找出陣列（或鏈表）的中心點。讓我們來解釋一下：

假設有一個陣列（或鏈表），我們使用兩個指針A和B：

• A每次走兩步：A = A + 2
• B每次走一步：B = B + 1

當A無法再走兩步時（即A已經達到陣列的末尾或超出了範圍），這時B所在的位置通常會是整個陣列的中心點。這是因為A每次走兩步，B每次走一步，所以當A走到末尾時，B大概就是A所走過的一半路程。

  Linked List Cycle

快慢指針算法中，快指針每次移動兩步，慢指針每次移動一步，快指針會在某個時刻追上慢指針，這是檢測循環的有效策略。

class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: slow = fast = head while fast and fast.next: fast = fast.next.next slow = slow.next if slow == fast: return True return False

Q: 所以當slow和fast都為ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}} 就代表成還了?

A: 不完全正確。當我們說 slow 和 fast 是 ListNode 類型的變量時，它們實際上是指向鏈表中某個節點的指針，而不是鏈表中的整個節點。

讓我們澄清一下：

1. ListNode 的結構：

   • ListNode 是一個類型，用來表示鏈表中的每個節點。
   • 每個 ListNode 對象具有兩個屬性：
     • val：表示節點的值。
     • next：指向下一個節點的指針，如果是最後一個節點則為 None。

2. slow 和 fast 的意義：

   • slow 和 fast 是指向 ListNode 類型對象的指針。
   • 在解決鏈表問題時，slow 和 fast 指針分別指向鏈表中的某個節點，通常是從頭部開始。
   • 例如，如果鏈表的頭部是 head，則 slow 和 fast 可以初始化為 head，即 slow = head 和 fast = head。

3. 比較節點：

   • 當我們說 slow 和 fast 指向同一個節點時，例如 ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}，這意味著它們的指針都指向這個具體的節點物件。
   • 但在實際情況下，slow 和 fast 通常不會指向同一個節點，因為它們的遍歷速度不同（slow 每次移動一步，fast 每次移動兩步）。

4. 判斷是否有環：

   • 當使用快慢指針來判斷鏈表是否有環時，我們會遍歷鏈表並移動這兩個指針。
   • 如果存在環，fast 指針最終會追上 slow 指針，即它們會指向同一個節點，這時可以確定鏈表中存在環。
   • 如果不存在環，fast 指針會先到達鏈表尾部，即指向 None，此時 slow 和 fast 不會指向同一個節點。

總結來說，slow 和 fast 是用來遍歷和判斷鏈表結構的指針，它們不是鏈表中節點的整體表示，而是指向鏈表中特定節點的指標。

在上面提到的例子中：

• 如果我們設置 slow = head 和 fast = head，然後根據上述步驟移動指針，當 slow 和 fast 同時指向節點 ListNode{val: 4, next: None} 時，這意味著它們指向了同一個節點。
• 如果此時 slow == fast，則我們可以確定這個鏈表中存在環。

總結來說，節點的形式像 ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}} 只是用來表示鏈表的結構，而快慢指針 slow 和 fast 是實際用來遍歷和判斷鏈表是否有環的指針變量。

https://medium.com/@cutesciuridae/%E8%A7%A3%E9%A1%8C%E6%95%99%E5%AD%B8-leetcode-141-linked-list-cycle-9c99b54d8dd8

Q: 為何快指針一定是+2 而不是+3 or +4?

在檢測鏈表中是否有循環的算法中，通常快指針每次移動兩步的原因如下：

1. 效率與實用性考量：移動快指針兩步比起三步或四步更為高效。在大多數情況下，兩步的速度已經足夠快，同時也能確保快指針在遍歷鏈表時能夠在適當的時間內達到與慢指針的相遇條件。

2. 避免過度跳躍：如果快指針每次移動三步或更多步，可能會過度跳過慢指針，這樣就可能會錯過檢測循環的機會。兩步的間隔通常足夠大，可以有效地檢測出鏈表中的循環，同時也不會太過於頻繁地跳過節點。

3. 理論依據：在循環檢測算法中，證明了如果鏈表中有循環，快指針每次移動兩步時，會在某個時刻與慢指針相遇。這個算法的理論基礎已經被廣泛證明，並且在實踐中被廣泛使用。