0.7 链表

[160. 相交链表](https://leetcode.cn/problems/intersection-of-two-linked-lists/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def getIntersectionNode(
        self, headA: ListNode, headB: ListNode
    ) -> Optional[ListNode]:
        node1 = headA
        node2 = headB
        while node1 != node2:
            node1 = node1.next if node1 else headB
            node2 = node2.next if node2 else headA
        if node1 == node2:
            return node1
        return False
```
[206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre
```
[234. 回文链表](https://leetcode.cn/problems/palindrome-linked-list/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

pre = None
        cur = slow
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt

left, right = head, pre
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True
```
[141. 环形链表](https://leetcode.cn/problems/linked-list-cycle/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False
```
[142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                fast = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None
# 开始与环距离a
# 环口到第一次相遇b
# 第一次相遇到还口c
# fast：a + b + n(b+c)
# slow: a + b
# a + b + n(b+c) = 2(a+b) -> a = c + (n-1)(b+c)
```
[21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:return list2
        if not list2:return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2
```
[*2. 两数相加](https://leetcode.cn/problems/add-two-numbers/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        dummy = node = ListNode()
        remain = 0
        while l2 or l1:
            l1_val = l1.val if l1 else 0
            l2_val = l2.val if l2 else 0
            total = l1_val + l2_val + remain
            remain = total // 10
            node.next = ListNode(total % 10)
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
            node = node.next
        if remain != 0:
            node.next = ListNode(remain)
        return dummy.next
```
[19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        slow = fast = dummy
        for _ in range(n):
            fast = fast.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next
```
[24. 两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node = head
        for _ in range(2):
            if not node:
                return head
            node = node.next

pre = None
        cur = head
        for _ in range(2):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt

head.next = self.swapPairs(cur)
        return pre
```
[25. K 个一组翻转链表](https://leetcode.cn/problems/reverse-nodes-in-k-group/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    # 递归终止条件：剩余节点不足K个
        node = head
        for _ in range(k):
            if not node:
                return head
            node = node.next
        # 翻转当前K个节点
        pre = None
        cur = head
        for _ in range(k):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        # 连接后续递归结果
        head.next = self.reverseKGroup(cur, k)
        return pre
```
[138. 随机链表的复制](https://leetcode.cn/problems/copy-list-with-random-pointer/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        dic = {}
        node = head
        while node:
            dic[node] = Node(node.val)
            node = node.next
        node = head
        while node:
            dic[node].next = dic.get(node.next)
            dic[node].random = dic.get(node.random)
            node = node.next
        return dic[head]
```
[148. 排序链表](https://leetcode.cn/problems/sort-list/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

mid = slow.next
        slow.next = None
        l1 = self.sortList(head)
        l2 = self.sortList(mid)
        return self.merge(l1, l2)

def merge(self, l1, l2):
        if not l2:
            return l1
        if not l1:
            return l2
        if l1.val < l2.val:
            l1.next = self.merge(l1.next, l2)
            return l1
        else:
            l2.next = self.merge(l1, l2.next)
            return l2
```

[23. 合并 K 个升序链表]()
```python
class Solution:
    def mergeTwoList(self, l1, l2):
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val < l2.val:
            l1.next= self.mergeTwoList(l1.next, l2)
            return l1
        else:
            l2.next= self.mergeTwoList(l1, l2.next)
            return l2
    
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        n = len(lists)
        if n == 0:
            return None
        if n == 1:
            return lists[0]
        mid = n // 2
        left_half = self.mergeKLists(lists[:mid])
        right_half = self.mergeKLists(lists[mid:])
        return self.mergeTwoList(left_half,right_half)
```
```python
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        cur = dummy = ListNode()
        if len(lists) == 0:
            return None
        h = [(head.val, i) for i, head in enumerate(lists) if head]
        heapq.heapify(h)
        while h:
            v,i = heappop(h)
            cur.next = ListNode(v)
            cur = cur.next
            if lists[i].next:
                lists[i] = lists[i].next
                heapq.heappush(h, (lists[i].val,i))
        return dummy.next
```
[146. LRU 缓存]()
```python
class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)
```