两两交换链表节点
题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）
讲解链接：代码随想录 (programmercarl.com)
方法一：迭代模拟
关键点：
1、使用虚拟头节点，可以免于单独处理头两个翻转
2、每轮模拟维护一个cur，代表要反转的两个节点的前节点，两个节点可分别表示为cur.next和cur.next.next，然后按部就班
3、搞清楚每一步的指针变化顺序
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy_node=ListNode(next=head)
cur=dummy_node
while cur.next and cur.next.next:
fw=cur.next
bk=cur.next.next
nx=bk.next
bk.next=fw
cur.next=bk
fw.next=nx
cur=fw
return dummy_node.next
方法二：递归（可拓展为k个一组翻转）
关键点：
1、要明确递归函数的定义：将head为头结点的链表k个一组翻转并返回头结点
2、可以使用递归的关键：问题可分解为子问题
=>将前k个翻转+以第k+1个节点为头结点的链表k个一组翻转返回头结点+拼接
删除链表的倒数第 N 个结点
题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
讲解链接：代码随想录 (programmercarl.com)
关键点：双指针
1、使用虚拟头节点
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy_node=ListNode(next=head)
fast=dummy_node
slow=dummy_node
for i in range(n):
fast=fast.next
while fast.next!=None:
slow=slow.next
fast=fast.next
slow.next=slow.next.next
return dummy_node.next
链表交点
题目链接：面试题 02.07. 链表相交 - 力扣（LeetCode）
讲解链接：代码随想录 (programmercarl.com)
关键点：将两个链表尾部对齐
方法一：分别遍历计算长度差
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
lenA, lenB = 0, 0
cur = headA
while cur: # 求链表A的长度
cur = cur.next
lenA += 1
cur = headB
while cur: # 求链表B的长度
cur = cur.next
lenB += 1
curA, curB = headA, headB
if lenA > lenB: # 让curB为最长链表的头，lenB为其长度
curA, curB = curB, curA
lenA, lenB = lenB, lenA
for _ in range(lenB - lenA): # 让curA和curB在同一起点上（末尾位置对齐）
curB = curB.next
while curA: # 遍历curA 和 curB，遇到相同则直接返回
if curA == curB:
return curA
else:
curA = curA.next
curB = curB.next
return None
方法二：双指针
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
curA,curB=headA,headB
while curA and curB:
curA=curA.next
curB=curB.next
if curA:
while curA:
curA=curA.next
headA=headA.next
while headA:
if headA==headB:
return headA
headB=headB.next
headA=headA.next
elif curB:
while curB:
curB=curB.next
headB=headB.next
while headA:
if headA==headB:
return headA
headB=headB.next
headA=headA.next
else:
while headA:
if headA==headB:
return headA
headB=headB.next
headA=headA.next
return
环形链表
题目链接：142. 环形链表 II - 力扣（LeetCode）
讲解链接：代码随想录 (programmercarl.com)
关键点：快慢指针与数学计算
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast=head
slow=head
while True:
if not (fast and fast.next):
return None
fast=fast.next.next
slow=slow.next
if fast==slow:
break
fast=head
while fast!=slow:
fast=fast.next
slow=slow.next
return fast
