# **程式筆記(linked list)**
:::info
:information_source: 日期 : 2023/05/30
:::
**:thumbsup:** Data type (structure)
* Definition for singly-linked list
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
```
* dummy + tail
如果創建一個新的linked list
tail -> 遍歷到尾部
dummy -> dummy.next 回傳
```python
dummy = tail = ListNode()
```
* dummy
如果需要刪除第一個元素 (ex. Remove Nth Node From End of List) 可這樣定義
```python
dummy = ListNode(0, head)
```
一個程式只建立一個dummy node，其他node如果要相同位置，用引用的方式，不要再單獨建立另一個head前面的node
* 解題
快慢指針 -> 找中點(前長後短) / 找cycle
* NoneType
```python
'NoneType' object has no attribute 'next'
ex. tail = None, tail.next -> error
```
---
**:thumbsup:** 基本
* Reverse Linked List 反轉
```
(None)
pre -> head -> temp
步驟 : temp紀錄head的下一個 -> 更新head.next指向pre
-> 更新pre到head -> 更新head到temp
```
```python
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
while head:
temp = head.next
head.next = pre
pre = head
head = temp
return pre
```
* Merge Two Sorted Lists
```
創造dummy(頭)和tail(往下遍歷)
tail.next 指向小 list -> 更新 list = list.next -> 更新 tail = tail.next
* 因為會比較list1和list2 所以必須以兩個都存在為while條件
```
```python
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = tail = ListNode()
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
if list2:
tail.next = list2
return dummy.next
```
**快針慢指**
* Middle of the Linked List 找中間值
如果slow 當l1的最後一點，分離的兩個list會是前長後短
```python
1 - 2 - 3 / 4 - 5
1 - 2 / 3 - 4
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
```
* Linked List Cycle 是否有cycle循環
快針慢指
```python
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
```
---
**:thumbsup:** 多種基本組合
**刪除**
* Remove Nth Node From End of List 從尾端移除第n個數值
dummy必要，處理only one node, or removing the head of the list
```
dummy -> head 1 -> 2 -> ...
pre cur
cur 先移 n
cur / pre 一起移
pre 停在待刪字前一位
```
```python
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if not head:
return None
dummy = pre = ListNode(0, head)
cur = head
# pre-move n step
while n:
cur = cur.next
n -= 1
# move together
while cur:
cur = cur.next
pre = pre.next
pre.next = pre.next.next
return dummy.next
```
**串接**
* Reorder List 交叉串接
```
快慢指針找中點
反轉l2
l1和l2交續串接
```
in-place head
```python
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
# find middle
slow = fast = head
while fast and fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
list2 = slow.next
slow.next = None
# reverse list2
pre = None
while list2:
temp = list2.next
list2.next = pre
pre = list2
list2 = temp
# connect l1 and l2
l1, l2 = head, pre
while l1 and l2:
temp, temp2 = l1.next, l2.next
l1.next = l2
l2.next = temp
l1, l2 = temp, temp2
```
* Partition List
比x小的放前面，等於或比較大的放後面，也是串接
```python
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
small = small_tail = ListNode()
large = large_tail = ListNode()
while head:
if head.val < x:
small_tail.next = head
small_tail = small_tail.next
else:
large_tail.next = head
large_tail = large_tail.next
head = head.next
large_tail.next = None
small_tail.next = large.next
return small.next
```
* Odd Even Linked List 奇偶串接
```
偶數list : 偶數最後會指向None，會一起不通過while
1 -> 2 -> 3 -> 4 -> None
--
1 -> 3
2 -> 4 -> None (自帶)
--
odd_tail = 3
odd_tail.next = 4
odd_tail.next.next = None 跳出
--
兩者串接
奇數list : 奇數會正常接到數字(必定是多奇數)，偶數會指向None
1 -> 2 -> 3 -> 4 -> 5 -> None
--
1 -> 3
2 -> 4
odd_tail = 3 -> 4 -> 5
even_tail = 4 -> 5
--
3 -> 5
4 -> None
(1 -> 3 -> 5)
(2 -> 4 -> None)
odd_tail = 5
even_tail = None
--
odd_tail = 5
odd_tail.next = None 跳出
--
兩者串接
```
```python
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
even = even_tail = head.next
odd = odd_tail = head
while odd_tail and odd_tail.next and odd_tail.next.next:
odd_tail.next = even_tail.next # 3
odd_tail = odd_tail.next # 3
even_tail.next = odd_tail.next # can be None
even_tail = even_tail.next # 4
odd_tail.next = even
return odd
```
**快針慢指**
* Find the Duplicate Number 找重複的number
Floyd's Tortoise and Hare (Cycle Detection)
假設相遇在b和c交叉點，已知fast移動速度為slow的兩倍
fast = a + c + b + c
slow = a + c
2 * slow = fast
會得到結果是 **a = b**
再派兩個slow去走就好
```python
c(~~~~~~~~~
a(~~~~~~) ~
b(~~~...)(~~~
```
```python
def findDuplicate(self, nums: List[int]) -> int:
fast, slow = 0, 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow1 = 0
while True:
slow = nums[slow]
slow1 = nums[slow1]
if slow1 == slow:
break
return slow
```
* Linked List Cycle II
test case有沒迴圈的，需要回傳None
```python
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast = slow = head
while fast and fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
# check if fast reach the end
if not fast or not fast.next or not fast.next.next:
return None
slow2 = head
while slow and slow2:
if slow == slow2: # 需要再next前面 當開頭就是迴圈點
return slow
slow = slow.next
slow2 = slow2.next
```
**swap**
* Swap Nodes in Pairs
```
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Input: head = [1,2,3]
Output: [2,1,3]
```
```python
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = pre = ListNode(0, head)
while head and head.next:
n1, n2, n3 = head, head.next, head.next.next
pre.next = n2
n2.next = n1
n1.next = n3
head = n3
pre = n1
return dummy.next
```
---
**:thumbsup:** 應用
* Add Two Numbers 加法
正常加法
```
carry = total // 10
ans = total % 10
* l1 or l2 or carry 只要其中一個存在就要繼續下去
* 數字補0，list上補None
```
```python
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
carry = 0
dummy = tail = ListNode()
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = carry + val1 + val2
carry = total // 10
tail.next = ListNode(total % 10)
tail = tail.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
```
* Intersection of Two Linked Lists
```
計算長度
修正到同一個起跑點
一起移
```
```python
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
# count the length
l_a, l_b = 0, 0
a, b = headA, headB
while a:
a = a.next
l_a += 1
while b:
b = b.next
l_b += 1
# fix the length to the same starting line
a, b = headA, headB
while l_a > l_b:
a = a.next
l_a -= 1
while l_b > l_a:
b = b.next
l_b -= 1
# go through
while a and b:
if a == b:
return a
a = a.next
b = b.next
return None
```
* Merge k Sorted Lists
初始化放每個list的開頭，接著永遠pop調最小的(minHeap)，再新增該list的數字
heap : 需要i在裡面，當val相同時 pop出i小的數字，heap無法比較ListNode()
```python
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
minHeap = []
for i, l in enumerate(lists):
if l:
heapq.heappush(minHeap, (l.val, i, l))
dummy = tail = ListNode()
while minHeap:
val, i, l = heapq.heappop(minHeap)
tail.next = l
if l.next:
heapq.heappush(minHeap, (l.next.val, i, l.next))
tail = tail.next
return dummy.next
```
* Sort List 排序linked list
merge sort
先不停地把list切成左右兩半(快針慢指)，切分成一個一個最小linked的時候，再一個一個合併
```python
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# single element -> return element
if not head or not head.next:
return head
left, right = self.cutHalf(head)
left = self.sortList(left)
right = self.sortList(right)
return self.merge(left, right)
def cutHalf(self, head):
slow = fast = head
while fast and fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
right = slow.next
slow.next = None
return head, right
def merge(self, left, right):
dummy = tail = ListNode()
while left and right:
if left.val < right.val:
tail.next = left
left = left.next
else:
tail.next = right
right = right.next
tail = tail.next
if left:
tail.next = left
if right:
tail.next = right
return dummy.next
```
---
**:thumbsup:** 進階
* Rotate List
```
連接整個list
找到新頭+斷尾
```
base case : 空或只有一個數
```python
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# base case
if not head or not head.next:
return head
# connect tail with head, to make a rotated list
l = 1
tail = head
while tail.next:
tail = tail.next
l += 1
tail.next = head
# disconnect tail and head
pre = ListNode(0, head)
new_head = head
step = (l - k) % l # %l for speed up
while step:
pre = pre.next
new_head = new_head.next
step -= 1
pre.next = None
return new_head
```
* Remove Duplicates from Sorted List II
cur檢查現在這個跟接下來的有無重複數字
```python
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = tail = ListNode()
cur = head
while cur:
if cur and cur.next and cur.val == cur.next.val:
while cur and cur.next and cur.val == cur.next.val:
cur = cur.next
cur = cur.next # skip the last duplicate one
else:
tail.next = cur
cur = cur.next
tail = tail.next
tail.next = None
return dummy.next
```
* Flatten Binary Tree to Linked List
```python
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
self.reconnect(root)
def reconnect(self, node):
if not node:
return None
if not node.left and not node.right:
return node
left_tail = self.reconnect(node.left)
right_tail = self.reconnect(node.right)
if left_tail:
left_tail.right = node.right # 左尾接到右頭
node.right = node.left # 右頭改成左頭
node.left = None # 左頭指向空
return right_tail if right_tail else left_tail
```
---
**:thumbsup:** double linked list
* LRU Cache
```
DoubleLinkedlist :
需要initial L R
永遠加在最右邊
hashmap[key] = Node(key, val)
```
```python
class Node:
def __init__(self, key = -1, val = -1, pre = None, post = None):
self.key = key
self.val = val
self.pre = pre
self.post = post
class DoubleLinkedlist:
def __init__(self):
self.R = Node()
self.L = Node()
self.R.pre = self.L
self.L.post = self.R
def remove(self, node): # node on the linkedlist
# l <-> node <-> r
# l <-> r
l, r = node.pre, node.post
l.post = r
r.pre = l
return
def add(self, node): # add on the right
# l <-> R
# l <-> node <-> R
l = self.R.pre
l.post, self.R.pre = node, node
node.pre, node.post = l, self.R
return
class LRUCache:
def __init__(self, capacity: int):
self.record = {} # key : Node
self.dl = DoubleLinkedlist()
self.capacity = capacity
def get(self, key: int) -> int:
if key in self.record:
node = self.record[key]
self.dl.remove(node)
self.dl.add(node)
return node.val
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.record:
node = self.record[key]
node.val = value
self.dl.remove(node)
self.dl.add(node)
else: # add in cache
if len(self.record) == self.capacity: # reach limit
garbage = self.dl.L.post
self.dl.remove(garbage)
del self.record[garbage.key]
new_node = Node(key, value)
self.dl.add(new_node)
self.record[key] = new_node
return
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
```
---
**講解連結**
Provided by.
###### tags: `linked list` `note` `code`
Sign in with Wallet
Connect another wallet