---
# System prepended metadata

title: '**程式筆記(linked list)**'
tags: [linked list, code, note]

---

# **程式筆記(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 停在待刪字前一位
```
![image](https://hackmd.io/_uploads/SJff32IWke.png =60%x)

```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
![image](https://hackmd.io/_uploads/r1z-hBSbkx.png =50%x)


```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
![image](https://hackmd.io/_uploads/SJEO_XBZ1l.png =70%x)

比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 奇偶串接
![image](https://hackmd.io/_uploads/ByC_H7rWkx.png =50%x)

```
偶數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
![image](https://hackmd.io/_uploads/SJCCHn8b1e.png =60%x)

```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
```
計算長度
修正到同一個起跑點
一起移
```

![image](https://hackmd.io/_uploads/S1M6jaUWJx.png =70%x)

```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
![image](https://hackmd.io/_uploads/BkMRnMr-Je.png =50%x)

初始化放每個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檢查現在這個跟接下來的有無重複數字
![image](https://hackmd.io/_uploads/Bkfc_LSbye.png =70%x)

```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
![image](https://hackmd.io/_uploads/rJArkVdJyl.png =50%x)

```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`