本文介绍 LeetCode 题集中，有关链表的问题。
141. Linked List Cycle（环形链表）
问题描述
思路与代码
本题通过快慢指针追及问题的思路来解决。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
fast, slow = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
运行效果：
上述代码为二倍速的追及，实际上快指针的速度可以为慢指针的任何倍数。
三倍速的代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
fast, slow = head, head
while fast and fast.next and fast.next.next:
fast = fast.next.next.next
slow = slow.next
if fast == slow:
return True
return False
四倍速的代码：
class Solution:
def hasCycle(self, head: ListNode) -> bool:
fast, slow = head, head
while fast and fast.next and fast.next.next and fast.next.next.next:
fast = fast.next.next.next.next
slow = slow.next
if fast == slow:
return True
return False
运行效果并无明显差异。
142. Linked List Cycle II（环形链表 II）
问题描述
思路与代码
参考官方题解，本题有哈希表和快慢指针两种方法。
哈希表的方法相对容易理解：
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
set_visit = set()
set_visit.add(head)
while head:
if not head.next:
return None
if head.next in set_visit:
return head.next
else:
set_visit.add(head.next)
head = head.next
运行效果：
快慢指针法相对复杂：
快指针的速度为慢指针的 2 倍，当快慢指针相遇时，新定义一个指针指向起点，新指针与慢指针同时向前移动，速度相同，最终两者在入环点相遇。数学推导如下：
设快慢指针相遇时，慢指针在环中转了
k
1
k_1
k1? 圈，快指针转了
k
2
k_2
k2? 圈，故有：
(
a
+
k
1
?
b
+
c
)
?
2
=
a
+
k
2
?
b
+
c
?
a
=
(
k
2
?
2
?
k
1
)
?
b
?
c
(a + k_1 \cdot b + c) \cdot 2 = a + k_2 \cdot b + c \\ \ \\ a = (k_2 - 2 \cdot k_1) \cdot b - c
(a+k1??b+c)?2=a+k2??b+c?a=(k2??2?k1?)?b?c
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast, slow = head, head
while fast and slow:
if fast.next:
fast = fast.next.next
else:
return None
slow = slow.next
if fast == slow:
tmp = head
while tmp != slow:
tmp = tmp.next
slow = slow.next
return tmp
return None
运行效果：
206. Reverse Linked List（反转链表）
问题描述
思路与代码
本题有迭代法和递归法两种方法。
迭代法的思路比较简单，定义一个 pre 节点表示前一个节点，循环迭代即可。
代码如下：
# 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: ListNode) -> ListNode:
if not head or not head.next:
return head
pre = None # initialise pre
while head:
tmp = head.next # store head.next since head will change soon
head.next = pre # change head.next to pre
pre = head # pre move to head
head = tmp # head move to head.next using tmp
return pre
运行效果：
递归法理解起来有点麻烦，可以参考下面题解中的动图：
代码如下：
# 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: ListNode) -> ListNode:
def rec(node: ListNode):
if not node or not node.next:
return node
node_new = rec(node=node.next) # deepest invocation: return the tail as head after reversing
node.next.next = node # next of node.next point to current node
node.next = None # next of node set to None, will reset during pre recursion
return node_new
return rec(node=head)
运行效果：
92. Reverse Linked List II（反转链表 II）
问题描述
思路与代码
本题是前一题的变体，可以调用前一题的反转函数，完成片段内的反转，对于片段外的头尾部分拼接到反转后的片段前后即可。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
def reverse_linked_list(head: ListNode): # LeetCode 206, iteration type
pre = None
cur = head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
# use dummy node to store the head
dummy = ListNode(-1)
dummy.next = head
pre = dummy
# get the node before the left node
for _ in range(left - 1):
pre = pre.next
# get the right node
right_node = pre
for _ in range(right - left + 1):
right_node = right_node.next
left_node = pre.next # the left node
curr = right_node.next # next node of the right node
# cut off the period
pre.next = None
right_node.next = None
# reverse the period
reverse_linked_list(left_node)
# join back to the head and tail
pre.next = right_node
left_node.next = curr
return dummy.next
运行效果：
24. Swap Nodes in Pairs（两两交换链表中的节点）
问题描述
思路与代码
本题的思路与前两题相似，定义两个指针（节点），依次对每对节点进行反转，然后将指针向前移动两位，循环迭代即可。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummy = ListNode(val=-1)
dummy.next = head
pre = dummy
while pre.next and pre.next.next:
first, second = pre.next, pre.next.next
first.next = second.next
second.next = first
pre.next = second
pre = first # pre, move 2 steps to next couple
return dummy.next
运行效果：
