# 6. Linked List (11) - Python
> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
>
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)
<!-- 常用色碼紀錄
Easy: <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard: <font color="#ee2f56">**Hard**</font>
-->
## 1. Reverse Linked List
<font color="#00ad5f">**Easy**</font>
> Given the beginning of a singly linked list `head`, reverse the list, and return the new beginning of the list.
### Example 1:
```java
Input: head = [0,1,2,3]
Output: [3,2,1,0]
```
### Example 2:
```java
Input: head = []
Output: []
```
### Constraints
* `0 <= The length of the list <= 1000`.
* `-1000 <= Node.val <= 1000`
### Solution
:::info
此題可以當作反轉 linked list 的標準做法
:::
要做到 in-place 的反轉就需要有一個額外變數來暫存內容，類似變數的交換(swap)
* `resList` 表示反轉後的串列
* 初始化需要接地(ground)
* 每次迭代過程中負責接收原始串列的頭節點，再接上暫存串列 `temp`
* `temp` 用來暫存每次迭代過程中 `resList` 的結果
* 每次迭代結束後需要接回 `resList` 後端
* `head` 表示原始串列
* 迭代過程中頭節點被 `resList` 接走後需指向下一個節點的位置
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
resList = None # initialize the result
while head:
temp = resList
resList = head
head = head.next
resList.next = temp
return resList
```
## 2. Merge Two Sorted Lists
<font color="#00ad5f">**Easy**</font>
> You are given the heads of two sorted linked lists `list1` and `list2`.
>
> Merge the two lists into one sorted linked list and return the head of the new sorted linked list.
>
> The new list should be made up of nodes from `list1` and `list2`.
### Example 1:
```java
Input: list1 = [1,2,4], list2 = [1,3,5]
Output: [1,1,2,3,4,5]
```
### Example 2:
```java
Input: list1 = [], list2 = [1,2]
Output: [1,2]
```
### Example 3:
```java
Input: list1 = [], list2 = []
Output: []
```
### Constraints
* `0 <= The length of the each list <= 100`.
* `-100 <= Node.val <= 100`
### Solution
創建一個空的節點(dummy node)並用 `resList` 指標用來指向串列開頭，另一個指標用來 `lastNode` 用來追蹤每次迭代過程中的串列尾端。
因為兩個串列都是已經排序過的，所以當其中一個串列到達尾端時就可以跳離迴圈。剩下的串列直接完整接在後面即可。
因為 `resList` 與 `lastNode` 是屬同一個串列，但指向不同的節點，前者指向開頭的 dummy node 後者指向串列尾端，因此最後回傳原始串列的開頭節點 `resList.next`。
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
resList = lastNode = ListNode()
while (list1 and list2):
if (list1.val < list2.val):
lastNode.next = list1 # node point to smaller node
list1 = list1.next # update list1
else:
lastNode.next = list2
list2 = list2.next
lastNode = lastNode.next # update the pointer lastNode to point the last node
# concatenate the rest list when one of these lists finish
if (list1): # list 1 is rest
lastNode.next = list1
else:
lastNode.next = list2
return resList.next
```
:::info
`resList` 與 `lastNode` 只是一個用來儲存某個節點的變數，類似 C 語言中的 pointer 概念一樣。例如 `node = node.next` 只是代表 `node` 指標往後移動到下一個節點的位置。
:::
## 3. Reorder List
<font color="#ffbb00">**Medium**</font>
> You are given the head of a singly linked-list.
>
> The positions of a linked list of `length = 7` for example, can intially be represented as:
>
> `[0, 1, 2, 3, 4, 5, 6]`
>
> Reorder the nodes of the linked list to be in the following order:
>
> `[0, 6, 1, 5, 2, 4, 3]`
>
> Notice that in the general case for a list of `length = n` the nodes are reordered to be in the following order:
>
> `[0, n-1, 1, n-2, 2, n-3, ...]`
>
> You may not modify the values in the list's nodes, but instead you must reorder the nodes themselves.
### Example 1:
```java
Input: head = [2,4,6,8]
Output: [2,8,4,6]
```
### Example 2:
```java
Input: head = [2,4,6,8,10]
Output: [2,10,4,8,6]
```
### Constraints
* `1 <= Length of the list <= 1000`
* `1 <= Node.val <= 1000`
### Solution
假設節編號為 [1, 2, 3, 4, 5, 6, 7]，則重新排序後的節點編號為 [1, 7, 2, 6, 3, 4, 5]，也就是頭尾頭尾交錯排列。因為頭尾交錯排列。所以可以將整個陣列切成兩半後交錯接合。
根據上述規則可以整理出以下解題順序：
* 找到中間節點將串列分割
* 再將後半部的串列反轉
* 最後將前半部的串列(first)與反轉後的後半串列(revSecond)交錯合併
中間節點的尋找可以使用快慢指標(two pointer)進行，快指標每次跳兩個節點，慢指標每次跳一個節點，當快指標到達尾端時慢指標就會剛好指到中間位置。
中間有個小巧思是 slowPointer 找到中間節點後，中間節點的下一個才是 second 串列的頭。當找到 second 串列的頭之後需要再把 first 串列切斷(split)
最後兩個串列交錯互接時，因為一旦頭節點的後端被接走，就無法在找到第二節點的位置，所以需要先把第二節點用其他指標指向，再開始交錯互接。
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
# find the middle node
slowPointer, fastPointer = head, head.next
while fastPointer and fastPointer.next:
slowPointer = slowPointer.next # increasing by 1 step
fastPointer = fastPointer.next.next # increasing by 2 steps
second = slowPointer.next # slowPointer is the end of first, so the next is second
slowPointer.next = None # split the two list
# reverse the second list
revSecond = None
while second:
temp = revSecond
revSecond = second
second = second.next
revSecond.next = temp
first, second = head, revSecond
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
```
## 4. Remove N-th Node From End of List
<font color="#ffbb00">**Medium**</font>
> You are given the beginning of a linked list `head`, and an integer `n`.
>
> Remove the `nth` node from the end of the list and return the beginning of the list.
### Example 1:
```java
Input: head = [1,2,3,4], n = 2
Output: [1,2,4]
```
### Example 2:
```java
Input: head = [5], n = 1
Output: []
```
### Example 3:
```java
Input: head = [1,2], n = 2
Output: [2]
```
### Constraints
* The number of nodes in the list is `sz`.
* `1 <= sz <= 30`
* `0 <= Node.val <= 100`
* `1 <= n <= sz`
### Solution
#### 1. Iteration
注意題目要找的是刪除倒數第 $i$ 個。但因為 Singly linked list 的性質就是必須從頭開始才能歷遍所有節點。所以由串列起點開始計算，倒數第 $i$ 個節點其實是從頭開始算的第 $(n+1)-i$ 個節點，其中 $n$ 為串列長度。
此外，因為刪除指定節點後，後面的節點就會斷掉。因此應該是走訪到指定前點的前一個，再將指定節點的下一個節點連接到指定節點的前一個，完成刪除節點的動作。因為題目並沒有給串列長度為何，所以必須先找串列長度。具體步驟如下：
* 歷遍串列計算串列長度
* 再次歷遍找指定節點
在刪除節點階段，是透過 count 變數的迭加計算來確認是否抵達指定節點。count 的初始值是 1 表示當前指向第一個節點。但是，考慮到如果串列只有一個節點的話，則不會有指定節點的後一個節點。所以如果要刪除的是只有單一節點(totalNode=1)的串列的第一個節點就需要分開討論。
```python=
# Iteration ver.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# find the length of list
total = 0
temp = head
while (temp):
temp = temp.next
total += 1
targetNode = (total + 1) - n
count = 1 # curret node
ptr = head
while (count <= targetNode):
if targetNode == 1: # delete the first node
head = head.next
return head
if count == targetNode - 1:
ptr.next = ptr.next.next
return head
else:
ptr = ptr.next
count += 1
```
#### 2. Tow pointer
## 5. Copy Lst With Random Pointer
<font color="#ffbb00">**Medium**</font>
> You are given the head of a linked list of length `n`. Unlike a singly linked list, each node contains an additional pointer `random`, which may point to any node in the list, or `null`.
>
> Create a deep copy of the list.
>
> The deep copy should consist of exactly `n` new nodes, each including:
>
> * The original value `val` of the copied node
> * A `next` pointer to the new node corresponding to the `next` pointer of the original node
> * A `random` pointer to the new node corresponding to the `random` pointer of the original node
>
> Note: None of the pointers in the new list should point to nodes in the original list.
>
> Return the head of the copied linked list.
>
> In the examples, the linked list is represented as a list of `n` nodes. Each node is represented as a pair of `[val, random_index]` where `random_index` is the index of the node (0-indexed) that the `random` pointer points to, or `null` if it does not point to any node.
### Example 1:
```java
Input: head = [[3,null],[7,3],[4,0],[5,1]]
Output: [[3,null],[7,3],[4,0],[5,1]]
```
### Example 2:
```java
Input: head = [[1,null],[2,2],[3,2]]
Output: [[1,null],[2,2],[3,2]]
```
### Constraints
* `0 <= n <= 100`
* `-100 <= Node.val <= 100`
* `random` is `null` or is pointing to some node in the linked list.
### Solution
* 在迭代過程中一邊迭代一邊複製
* 困難點在於 random pointer 的 link，因為有些節點的 random link 所指向的位置可能尚未被建立/複製
* 但可以用一個 data structure 事先儲存這些節點的資訊(val, next, random)
* 每個對應的節點資訊要相同，可以使用 hash map
需要注意的是 hash map 的初始值需設置為 `{None:None}`，因為當某個原始節點是 `Null` 時，可能會沒有對應的複製的內容，導致取值錯誤。
```python=
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
orgToNew = {None:None}
currentNode = head
# iterate the whole list and copy each node
while currentNode:
orgToNew[currentNode] = Node(currentNode.val)
currentNode = currentNode.next
# concatenate the link and random
currentNode = head
while currentNode:
copiedNode = orgToNew[currentNode]
copiedNode.next = orgToNew[currentNode.next]
copiedNode.random = orgToNew[currentNode.random]
currentNode = currentNode.next
return orgToNew[head]
```
## 6. Add Two Numbers
<font color="#ffbb00">**Medium**</font>
> You are given two **non-empty** linked lists, `l1` and `l2`, where each represents a non-negative integer.
>
> The digits are stored in **reverse order**, e.g. the number 123 is represented as `3 -> 2 -> 1 ->` in the linked list.
>
> Each of the nodes contains a single digit. You may assume the two numbers do not contain any leading zero, except the number 0 itself.
>
> Return the sum of the two numbers as a linked list.
### Example 1:
```java
Input: l1 = [1,2,3], l2 = [4,5,6]
Output: [5,7,9]
Explanation: 321 + 654 = 975.
```
### Example 2:
```java
Input: l1 = [9], l2 = [9]
Output: [8,1]
```
### Constraints
* `1 <= l1.length, l2.length <= 100`
* `0 <= Node.val <= 9`
### Solution
* 依照一般加法的方式依序操作，勿忘過程中可能需要進位(carry)
* 初始化進位的變數 `carry = 0`
```python=
# space complexity = O(max(m, n))
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
ptr = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
# new digit
val = v1 + v2 + carry
carry = val // 10
val = val % 10
ptr.next = ListNode(val=val)
# update pointer
ptr = ptr.next
l1 = l1.next if l1 else None # the condition is l1 instead of l1.next since l1.next may be nothing if l1 is NULL
l2 = l2.next if l2 else None
return dummy.next
```
解答給的方法的空間複雜度實際上是 $O(\max(m,n))$，因為會新建立一個串列來儲存這些相加後的值。
如果要做到真的的 $O(1)$ 空間複雜度(in-place)就需要把相加後的結果儲存在某個輸入串列中(通常是較長的那個)，但最後會遇到的問題是
* 串列都加完了，但還有進位(carry)數字沒有處理，Ex: 9 + 9 = 18
* 此時雖然新建立的節點可以儲存 carry 值，但無法接上前一個節點，因為輸入的兩個串列此時都走訪到 NULL
* 所以必須要有一個指標來追蹤前一個節點的位址
## 7. Linked List Cycle
<font color="#00ad5f">**Easy**</font>
> Given the beginning of a linked list `head`, return `true` if there is a cycle in the linked list. Otherwise, return `false`.
>
> There is a cycle in a linked list if at least one node in the list that can be visited again by following the `next` pointer.
>
> Internally, `index` determines the index of the beginning of the cycle, if it exists. The tail node of the list will set it's `next` pointer to the `index-th` node. If `index = -1`, then the tail node points to `null` and no cycle exists.
>
> **Note:** `index` is **not** given to you as a parameter.
### Example 1:
```java
Input: head = [1,2,3,4], index = 1
Output: true
```
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
### Example 2:
```java
Input: head = [1,2], index = -1
Output: false
```
### Constraints
* `1 <= Length of the list <= 1000`
* `-1000 <= Node.val <= 1000`
* `index` is `-1` or a valid index in the linked list.
### Solution
#### 1. 使用 list
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
traversalNode = []
while head:
traversalNode.append(head)
if head.next in traversalNode:
return True
head = head.next
return False
```
使用一個串列 `traversalNode` 來儲存走訪過的節點位址，空間複雜度為 $O_s(n)$。缺點是串列的搜尋需要 $O(n)$ 的時間複雜度。要降低查找的時間可以使用 hash map 或 hash set 的結構來儲存，因為 hash 的結構可以做到搜尋時間為 $O(1)$。
#### 2. Hash map
```python=
# hash map
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
visitCount = {}
while head:
visitCount[head] = visitCount.get(head, 0) + 1
if visitCount[head] > 1:
return True
head = head.next
return False
```
使用一個 hash map 來儲存每個節點出現的對應次數，只要在歷遍節點的過程中，某個節點的出現次數 > 1 次就代表串列有 cycle 的結構。
#### 3. Two pointers
使用快慢指標的方式可以做到空間複雜度為 $O(1)$。`fastPointer` 與 `slowPointer` 初始化指向的位址相同，都是串列的開頭。不同的是 `fastPointer` 的速度是 `slowPointer` 的兩倍，前者每次走兩步，後者走一步。
在某個時間點如果 `fastPointer` 與 `slowPointer` 指向的位置相同，代表串列有 cycle 的結構。以 Example 1 的輸入串列為例：
| Time | slowPointer | fastPointer | Remark |
| :-: | :-: | :-: | :-: |
| 0 | 1 | 1 |
| 1 | 2 | 3 |
| 2 | 3 | 2 |
| 3 | 4 | 4 | **meet** |
> **Proof :** Why the list have cycle when these two pointers meet.
> <img src="https://hackmd.io/_uploads/S1brS53E1e.png" width=400>
> 以上圖所示，因為 fastPointer 需要去追趕 slowPointer，所以假設在環狀結構中 fastPointer 與 slowPointer 的距離為 $d$。
> 因為 fastPointer 的速度是 slowPointer 的兩倍，所以兩者在環狀結構中必定會相遇，且所需時間(t)為
> $$
> t = \frac{d}{2 - 1} = d
> $$
```python=
# two pointer
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slowPointer = fastPointer = head
while fastPointer and fastPointer.next:
# 一開始必須先往前走，因為初始化兩者是指向相同的節點
slowPointer = slowPointer.next
fastPointer = fastPointer.next.next
if slowPointer == fastPointer:
return True
return False
```
## 8. Find The Duplicate Number
<font color="#ffbb00">**Medium**</font>
> You are given an array of integers `nums` containing `n + 1` integers. Each integer in `nums` is in the range ``[1, n]`` inclusive.
>
> Every integer appears exactly once, except for one integer which appears **two or more times**. Return the integer that appears more than once.
**keywoed:** Floyd's Cycle Detection
### Example 1:
```java
Input: nums = [1,2,3,2,2]
Output: 2
```
### Example 2:
```java
Input: nums = [1,2,3,4,4]
Output: 4
```
### Constraints
* `1 <= n <= 10000`
* `nums.length == n + 1`
* `1 <= nums[i] <= n`
### Recommended complexity
* Time complexity: $O(n)$
* Space complexity: $O(1)$
### Solution
此題事實上應該歸類在 <font color="#ee2f56">**Hard**</font> 才對。
題目給定的串列可以看成是一個 linked list，每個節點的內容代表的是指向的下一個位置。以 `[1, 2, 3, 2, 2]` 的串列為例，第一個節點的內容是 1，代表指向 index = 1 的位置，後續依此推類，畫成 linked list 後如下圖所示。
要判斷有沒有重複的數字，只要判斷給定的串列會不會形成一個 cycle，要判斷有沒有 cycle，只要能夠找到 cycle 的開頭即可。
:::info
Cycle 的開頭就是重複的數字
:::
<img src="https://hackmd.io/_uploads/BJZSpJESJg.png" width=500>
而要判斷尋找 cycle 的開頭，可以使用 Floyd's Cycle Detection
> **Floyd's Cycle Detection**
> 交點與 cycle head 的距離 = 起點與 cycle head 的距離
以下圖為例：
* 給定一組快慢指標 `f` 與 `s1`，`f` 的速度是 `s` 的兩倍
* 這兩個指標先去找第一個交點(4))
* 當找到第一個交點時，再設定另一個慢指標 `s2` 從原點起步
* 第一慢指標 `s1` 從交點處(4)往前一步，第二個慢指標 `s2` 從起點(1)往前一步
* 當兩個慢指標相交(2)，則此交點就是 cycle 的開頭
> **Proof**
> 如圖所示，已知 cycle length = c，起點與 cycle head 距離為 p，第一交點與 cycle head 距離為 x，試證 $p = x$
>
> 設 `s` 走的距離是
> $$
> p + (c - x) + p
> $$
> `f` 走的距離是
> $$
> p + c + (c - x)
> $$
> 因為快指標速度是慢指標 2 倍，所以
> $$
> \begin{align}
> 2 \cdot \text{s} &= \text{f}\\
> 2 \cdot (p + c - x) &= p + c + (c - x)\\
> p &= x
> \end{align}
> $$
> 
```python=
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# meet at first intersection
slowPointer, fastPointer = 0, 0
while True:
slowPointer = nums[slowPointer] # 1 step
fastPointer = nums[nums[fastPointer]] # 2 step
if slowPointer == fastPointer:
break
# meet at second intersection
secSlowPointer = 0
while True:
slowPointer = nums[slowPointer]
secSlowPointer = nums[secSlowPointer]
if slowPointer == secSlowPointer:
return slowPointer
```
## 9. LRU cache
<font color="#ffbb00">**Medium**</font>
> Implement the [Least Recently Used (LRU)](https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU) cache class `LRUCache`. The class should support the following operations
>
> * `LRUCache(int capacity)` Initialize the LRU cache of size `capacity`.
> * `int get(int key)` Return the value cooresponding to the `key` if the `key` exists, otherwise return `-1`.
> * `void put(int key, int value)` Update the `value` of the `key` if the `key` exists. Otherwise, add the `key`-`value` pair to the cache. If the introduction of the new pair causes the cache to exceed its capacity, remove the least recently used key.
>
> A key is considered used if a `get` or a `put` operation is called on it.
>
> Ensure that `get` and `put` each run in $O(1)$ average time complexity.
### Example 1:
```java
Input:
["LRUCache", [2], "put", [1, 10], "get", [1], "put", [2, 20], "put", [3, 30], "get", [2], "get", [1]]
Output:
[null, null, 10, null, null, 20, -1]
Explanation:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 10); // cache: {1=10}
lRUCache.get(1); // return 10
lRUCache.put(2, 20); // cache: {1=10, 2=20}
lRUCache.put(3, 30); // cache: {2=20, 3=30}, key=1 was evicted
lRUCache.get(2); // returns 20
lRUCache.get(1); // return -1 (not found)
```
### Constraints
* `1 <= capacity <= 100`
* `0 <= key <= 1000`
* `0 <= value <= 1000`
### Recommended complexity
* Time complexity: $O(1)$ for `put()` and `get()`
* Space complexity: $O(n)$ overall
### Solution
需要某個結構能儲存 (key, value) pair :arrow_right: Hash map
需要某個結構能儲存使用順序，且要能做到在 $O(1)$ 的時間內刪除與插入 :arrow_right: Doubly linked list
:::info
**為何 doubly linked list 能保證刪除節點時能做到 $O(1)$ 的時間？**
因為如果使用 singly linked list 就必須知道前一個節點的位置，那就需要走訪整個串列才能知道。
:::
以 doubly linked list 搭配 hash map 實作 LRU cache，最近用過的資料會被放在 list 尾端，不常使用的資料會放在 list 開頭。
* 每當資料額滿但要新增資資料就從 list 的頭端刪除並從尾端新增
* 都有某個資料被使用時，要把這個資料取出並再次插入 list 尾端，代表最近使用過它。
Hash map 的作用是為了方便尋找要使用/刪除/移動的節點， key 是儲存輸入的 key，value 是儲存節點。
此外，節點中的除了值以外也必須儲存輸入的 key，保持跟 hash map 的一致性，才能在 list 刪除節點後把 hash map 中對應的節點一併刪除。
```python=
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.LP, self.RP = None, None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # map key to node
# create two dummy node as head and tail
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.RP = self.tail
self.tail.LP = self.head
def remove(self, node):
""" remove particular node """
leftNode = node.LP
rightNode = node.RP
leftNode.RP = rightNode
rightNode.LP = leftNode
def insert(self, node):
""" insert node at tail """
self.leftNode = self.tail.LP
node.LP = self.leftNode
node.RP = self.tail
self.leftNode.RP = node
self.tail.LP = node
def get(self, key: int) -> int:
if key in self.cache:
self.remove(self.cache[key]) # remove the node
self.insert(self.cache[key]) # then update its location to the tail
return self.cache[key].val
else:
return -1
def put(self, key: int, value: int) -> None:
# no matter the node exist in list
# we must add/update this node into list
if key in self.cache:
self.remove(self.cache[key])
self.cache[key] = Node(key, value)
self.insert(self.cache[key])
if len(self.cache) > self.capacity:
LRU = self.head.RP
self.remove(LRU)
del self.cache[LRU.key]
```
#### Reference
* [資料結構與演算法：LRU 快取機制](https://josephjsf2.github.io/data/structure/and/algorithm/2020/05/09/LRU.html)
## 10. Merge K Sorted Lists
<font color="#ee2f56">**Hard**</font>
> You are given an array of `k` linked `lists` lists, where each list is sorted in ascending order.
>
> Return the **sorted** linked list that is the result of merging all of the individual linked lists.
### Example 1:
```java
Input: lists = [[1,2,4],[1,3,5],[3,6]]
Output: [1,1,2,3,3,4,5,6]
```
### Example 2:
```java
Input: lists = []
Output: []
```
### Example 3:
```java
Input: lists = [[]]
Output: []
```
### Constraints
* `0 <= lists.length <= 1000`
* `0 <= lists[i].length <= 100`
* `-1000 <= lists[i][j] <= 1000`
### Recommended complexity
* Time complexity: $O(n \cdot k)$
* Space complexity: $O(1)$
### Solution
題目給的輸入串列總共儲存了 k 個 linked list，每個 index 代表的是 linked list 的開頭。解題方式也很簡單，就是從頭開始走訪輸入串列，並倆倆倆合併，如下圖所示。
<img src="https://hackmd.io/_uploads/H14ZZWNSke.png" width = 500>
要注意的是在走訪輸入串列的時候，因為是兩兩一組合併，所以控制變數是依照 0, 2, 4, ... 的順序(step=2)。
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:
return None
while len(lists) > 1:
mergedList = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if (i + 1) < len(lists) else None
mergedList.append(self.mergeTwoLists(l1, l2))
lists = mergedList
return lists[0]
def mergeTwoLists(self, list1, list2):
dummy = ListNode()
ptr = dummy
while list1 and list2:
if list1.val < list2.val:
ptr.next = list1
list1 = list1.next
else:
ptr.next = list2
list2 = list2.next
ptr = ptr.next
if list1 is None:
ptr.next = list2
else:
ptr.next = list1
return dummy.next
```
## 11. Reverse Nodes in K Group
<font color="#ee2f56">**Hard**</font>
> You are given the head of a singly linked list `head` and a positive integer `k`.
>
> You must reverse the first `k` nodes in the linked list, and then reverse the next `k` nodes, and so on. If there are fewer than `k` nodes left, leave the nodes as they are.
>
> Return the modified list after reversing the nodes in each group of `k`.
>
> You are only allowed to modify the nodes' `next` pointers, not the values of the nodes.
### Example 1:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/67cf2fff-f20a-4558-6091-c3e857f56e00/public" width=500>
```java
Input: head = [1,2,3,4,5,6], k = 3
Output: [3,2,1,6,5,4]
```
### Example 2:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/af843e59-df12-4c55-652b-6ddab0a92900/public" width=500>
```java
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
```
### Constraints:
* The length of the linked list is `n`
* `1 <= k <= n <= 100`
* `0 <= Node.val <= 100`
### Recommended complexity
* Time complexity: $O(n)$
* Space complexity: $O(1)$
### Solution
每 k 個節點斷開，並反轉這 k 個節點，反轉後在接上後面的串列(step-by-step)：
* 找第 k 個
* 反轉前 k 個
* **接上第 k+1 個**
前兩步驟其實並不是太難，關鍵點是要如何將反轉後的串列接上第 k+1 個，並繼續此步驟？
以 group 代表目前正在處理的 k 個節點，`groupPrev` 代表這 k 個的前一個節點，`groupNext` 代表這 k 個的下一個節點。
反轉後，原始頭端(反轉後的尾端)已經接上下一個 group 的頭了，所以要處理的只有原始尾端(反轉後頭端)要接上 `groupPrev`。這其實就類似交換(swap)變數的概念，把原始的頭端(i.e., 反轉後的尾端，`groupPrev.next` )以一個中間變數替換追蹤，再把原始尾端(反轉後頭端)銜接上 `groupPrev.next` 即可。最後再把 `groupPrev` 移動到下一個 group 的位置繼續上述三個步驟。
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head) # dummy -> head
groupPrev = dummy # groupPrev/dummy -> head
while True:
kth = self.getKth(groupPrev, k)
if not kth:
break
groupNext = kth.next # the head of next group
# (1) revList
# revList initialize NULL generally
# but we must connect the next group head
# so we let revList initialize kth.next
# (2) ptr
# ptr is the head list we want to reverse
revList, ptr = kth.next, groupPrev.next
while ptr != groupNext:
temp = revList
revList = ptr
ptr = ptr.next
revList.next = temp
# we must connect to the last node of previous group
# then update to the next group
# remember that the original head is end of reverse group
# it also the previous node of next group head
temp = groupPrev.next # original head
groupPrev.next = kth # reverse head
groupPrev = temp
return dummy.next
def getKth(self, cur, k):
while cur and k > 0:
cur = cur.next
k -= 1
return cur
```
Sign in with Wallet
Connect another wallet