快慢指针

2026-01-31

1. 链表的中间节点

（876）给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
   def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
       s,f = head,head
       while f and f.next:
           s = s.next
           f = f.next.next
       return s

2. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ，则返回 true 。否则，返回 false 。

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
   def hasCycle(self, head: Optional[ListNode]) -> bool:
       s,f=head,head
       while f and f.next:
           s,f = s.next,f.next.next
           if s is f:
               return True
       return False

3. 环形链表II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
   def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
       s,f = head,head
       while f and f.next:
           s,f = s.next,f.next.next
           if s is f:
               while s!=head:
                   s,head = s.next,head.next
               return head
       return None

4. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为： L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为： L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

输入：head = [1,2,3,4]
输出：[1,4,2,3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

```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:
       """
       Do not return anything, modify head in-place instead.
       """
       mid = self.midnode(head)
       head2 = self.reverselist(mid)
       while head2.next:
           nxt = head.next
           nxt2 = head2.next
           head.next = head2
           head2.next = nxt
           head = nxt
           head2 = nxt2

   def midnode(self,head):
       s,f = head,head
       while f and f.next:
           s,f = s.next, f.next.next
       return s
   def reverselist(self,head):
       pre = None
       cur = head
       while cur:
           nxt = cur.next
           cur.next = pre
           pre = cur
           cur = nxt
       return pre