---
# System prepended metadata

title: 链表
tags: [Summary]

---

---
tags: Summary
---

# 链表

### 定义

```python=
class ListNode:
    def __init__(self, x, next=None):
        self.val = x
        self.next = next
```

---

**1. 环形链表**

检测链表中的环

[141. 环形链表](https://leetcode-cn.com/problems/linked-list-cycle/)

```
1 -> 2 -> 3 -> 4
     |         |
     7 <- 6 <- 5
```
     
快慢指针，相撞即有环

```python=
def hasCycle(head: ListNode) -> bool:
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            return True
    return False
```

---

**2. 环形链表 II**

检测链表中的环，并输出入环的第一个结点，无环返回 None

[142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)

先快慢指针检测是否有环，然后将 ptr 放到 head，同时开始 ptr 和 slow，相撞的点即为入环点

证明：设入环点前长度为 a，slow 走过的路程为 a + b，fast 走过的路程为 a + n(b + c) + b（n 为圈数，b + c 为环长）
fast 的路程一定是 slow 的两倍，所以 a + n(b + c) + b = 2a + 2b
所以 a = (n - 1)(b + c) + c

```python=
def detectCycle(head: ListNode) -> ListNode or None:
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            ptr = head
            while ptr != slow:
                slow = slow.next
                ptr = ptr.next
            return ptr
    return None
```

---

**3. 相交链表**

找到两个单链表相交的起始结点

[160. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/)

```
1 -> 2 -> 3
          |
4 -> 5 -> 6 -> 7
```

双指针，相遇

时间 O(n) 空间 O(1)

```python=
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode or None:
    nodeA, nodeB = headA, headB
    while nodeA != nodeB:
        nodeA = nodeA.next if nodeA else headB
        nodeB = nodeB.next if nodeB else headA
    return nodeA
```

---

**4. 链表的中间结点**

找出单链表的中间结点

[876. 链表的中间结点](https://leetcode-cn.com/problems/middle-of-the-linked-list/)

```
1 -> 2 -> 3 -> 4 -> 5
          |
```

快慢指针，快的到链表尾，慢的即在中点

```python=
def middleNode(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    return slow
```

---

**5. 反转链表**

反转一个单链表

[206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/)

双指针

```python=
def reverseList(head: ListNode) -> ListNode:
    pre, curr = None, head
    while curr:
        curr.next, pre, curr = pre, curr, curr.next
    return pre
```

---

**6. K 个一组反转链表**

困难

将一个链表每 k 个结点一组进行反转，返回反转后的链表

input: 1 -> 2 -> 3 -> 4 -> 5;  k = 2

output: 2 -> 1 -> 4 -> 3 -> 5

时间 O(n) 空间 O(1)

```python=
def reverseKGroup(head: ListNode, k: int) -> ListNode:
    def reverse(one_head: ListNode, one_tail: ListNode) -> (ListNode, ListNode):
        pre, curr = None, one_head
        while pre != one_tail:
            curr.next, pre, curr = pre, curr, curr.next
        return one_tail, one_head

    pre = dummy = ListNode(0, next=head)
    curr = head
    while curr:
        for _ in range(k - 1):
            curr = curr.next
            if curr is None:
                return dummy.next
        one_head, one_tail, curr = pre.next, curr, curr.next  # 确定下一步要 reverse 的头尾
        one_head, one_tail = reverse(one_head, one_tail)  # reverse
        pre.next, one_tail.next = one_head, curr  # 连接
        pre = one_tail  # 把 pre 移动到下一次的位置
    return dummy.next
```

---

**7. 合并两个有序链表**

input: 1 -> 2 -> 4; 1 -> 3 -> 4

output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

```python=
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    n1 = dummy = ListNode(0, next=l1)
    n2 = l2
    while n1.next and n2:
        if n1.next.val >= n2.val:
            n1.next, n2 = n2, n1.next
        n1 = n1.next
    if n2:
        n1.next = n2
    return dummy.next
```

---

**8. 合并 K 个有序链表**

input: 1 -> 4 -> 5; 1 -> 3 -> 4; 2 -> 6

output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

```python=
def mergeKLists(lists: list) -> ListNode:
    def merge2Lists(l1: ListNode, l2: ListNode) -> ListNode:
        n1 = dummy = ListNode(0, next=l1)
        n2 = l2
        while n1.next and n2:
            if n1.next.val >= n2.val:
                n1.next, n2 = n2, n1.next
            n1 = n1.next
        if n2:
            n1.next = n2
        return dummy.next

    def recur(ls: list) -> ListNode:
        if len(ls) == 0:
            return None
        if len(ls) == 1:
            return ls[0]
        mid = len(ls) // 2
        return merge2Lists(recur(ls[:mid]), recur(ls[mid:]))

    return recur(lists)
```


