前言
今天是算法训练营的第四天，今天的主题依旧是链表但是题目难度有所上升，经过几天的训练后，明显感觉到现在对于题目的想法增加了许多，绝非以往看到题目不会做就先去看题解，在学习题解思路的基础上也会想想有没有其他方法也能得到答案。
希望再过几天能够将 go 语言也运用到算法训练里，让 go 语言功底同步提升。
24.两两交换链表中的节点
题目链接：24. 两两交换链表中的节点
题目描述：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路
这道题的实现大致是在用代码模拟两两交换的步骤，假如有四个节点分别为1 2 3 4，那么两两交换后就是 2 1 4 3，通过观察后，我们可以进行步骤模拟。
首先，让 1 指向 4，再让 2 指向 1这样我们就完成了一对节点的两两交换，接下来循环到链表结束就好，这里的具体步骤还是用画图的方式更加直观一些。
模拟步骤实现写法
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummyHead = ListNode(None, head)
cur = dummyHead
while cur.next and cur.next.next:
temp = cur.next
temp2 = cur.next.next.next
cur.next = cur.next.next
cur.next.next = temp
cur.next.next.next = temp2
cur = cur.next.next
result = dummyHead.next
return result19.删除链表倒数第N个结点
题目链接：19. 删除链表的倒数第 N 个结点
题目描述：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
思路
这道题最终使用了两种思路得到两个解法：
- 解法一比较容易理解，首先遍历链表有多少个元素并进行记录，加入了虚拟头节点后，如果我们要删除倒数第N个元素，那么只要移动到第count – n 个节点的位置，再执行链表删除的基本操作就行
- 解法二比较巧妙，使用到了快慢指针的思想，定义一堆快慢指针，如果想删除倒数第N 个元素，那么只需要先让快指针比慢指针多跑N+1步，然后再让两个指针以相同的速度向后扫描，最后当快指针移动到末尾时，慢指针的位置正好就是倒数第N – 1 个节点，此时再进行链表基本删除操作就行
解法一实现写法：
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummyHead = ListNode(None, head)
cur = dummyHead
count = 0
while cur.next:
cur = cur.next
count += 1
cur = dummyHead
for i in range(count - n):
cur = cur.next
cur.next = cur.next.next
return dummyHead.next快慢指针实现写法：
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummyHead = ListNode(None, head)
slow = dummyHead
fast = dummyHead
for i in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummyHead.next02.07.链表相交
题目链接：面试题 02.07. 链表相交
题目描述：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路
刚见到这道题觉得有点似曾相识，疑似是半年前看到的莉莉丝笔试真题。因为熟悉，所以对这条题格外关注，最终使用到了三种解法来解决这道题。
- 解法一：在判断链表相交时，我们关注的不是节点的数值是否相等，而是两个节点是否相同，如果相同那么代表相交。关于这道问题，我们不妨假设 A 和 B 存在相交部分，那么我们将 A 和 B 连接到同一条链表上，由于速度相同但是走的路程不同，两者必然最终相交，并且第一次相交的位置就是交点。连到一条链表的逻辑是如果指针A走到链表A的末尾，那么下一步来到链表B的头部，链表B同理。
- 解法二：朴实无华的暴力，但是这里力扣使用大数据测试用例导致超时无法通过，具体步骤就是对A的每一个节点都让B循环一次判断在 B 上是否有相同节点，如果有那么就是交点。
- 解法三：解法三学习自卡尔文档，首先记录下两个链表的长度并进行比较，让更长的一条线移动lenthA-lenthB次（此处假设 A 长 B 短）， 这样一来两者在同一起点位置上，接下来两个指针以相同速度移动，如果出现节点相等那么说明两个链表相交。
解法一实现写法：
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None
pointerA = headA
pointerB = headB
# 两个指针同时遍历两个链表
# 当 pointerA 到达链表A末尾时，转到链表B的开头
# 当 pointerB 到达链表B末尾时，转到链表A的开头
# 这样两个指针会走过相同的总长度（A+B）
while pointerA != pointerB:
pointerA = pointerA.next if pointerA else headB
pointerB = pointerB.next if pointerB else headA
# 要么在交点相遇，要么都为 None（没有交点）
return pointerA解法二实现写法：
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
pointA = headA
while pointA:
pointB = headB
while pointB:
if pointA == pointB:
return pointA
pointB = pointB.next
pointA = pointA.next
return None 解法三实现写法
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
def ctlenth(head:ListNode) -> int:
count = 0
temp = head
while temp:
temp = temp.next
count += 1
return count
lenA = ctlenth(headA)
pointA = headA
lenB = ctlenth(headB)
pointB = headB
if lenA > lenB:
for i in range(lenA - lenB):
pointA = pointA.next
elif lenB > lenA:
for i in range(lenB - lenA):
pointB = pointB.next
while pointA:
if pointA == pointB:
return pointA
else:
pointA = pointA.next
pointB = pointB.next
return None142.环形链表II
题目链接：142. 环形链表 II
题目描述：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
思路
刚看到这题我第一反应觉得还挺简单的，答题思路可能和上一题差不多，然后草草写了个暴力做法，虽然说没有超时但执行用时超级长。然后看了下卡尔视频，学到的解法非常巧妙，最后也成功把执行用时压了百倍。
- 解法一：朴实无华的暴力，使用两个cur 指针，对每一个 cur1 都用cur2遍历链表进行比较节点是否相等，由于是在单个链表上进行比较，所以一旦出现有节点相同那么肯定是有环存在，并且这个节点就是环起点。
- 解法二：解法二就很有意思了，卡尔老师的视频分析的非常透彻，用一个类似操场跑步追及问题的模型来解决这个问题，定义一对快慢指针，快指针每次走两步，慢指针每次走一步，如果两者在后续出现了相遇，那么说明一定存在环，相遇原因是因为快指针套了慢指针圈。但是，到这里还没有结束，以上只说明存在环，想要找到环起点还需要将慢指针重新拉回头节点，如果快节点和慢节点出现相遇，那么相遇位置就是环起点，具体原因详见视频数学证明。
解法一实现写法：
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur1 = head
index1 = 0
while cur1:
cur2 = head
index2 = 0
while cur2 and index2 < index1:
if cur1 == cur2: # 如果遇到相同的节点
return cur1 # 说明有环
cur2 = cur2.next
index2 += 1
cur1 = cur1.next
index1 += 1
return None 解法二实现写法：
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None总结
到这里，链表部分的学习就暂时告一段落了，在第三天主要是学习了链表的基本概念和基本操作，第四天在此基础上更加需要深入思考实际的执行过程，我个人觉得完成链表相关题目（不只是链表）如果借助画图，会使得理解更加容易，能理解执行过程后需要做的事情就是还原执行的过程。
这一部分克服了我先前对链表的恐惧，通过添加虚拟头节点使得解题方便许多，而快慢指针的思想在这一部分经常出现，值得深入分析。
