目录
任务
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路
这是一道模拟的题，修改的指针较多，较复杂，需要弄清楚修改的顺序，细心的一步步修改。但是大体的思路还是不变，引入了虚拟节点，注意单次循环中的节点指针域变化。
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
cur = dummy
while cur and cur.next and cur.next.next:
oldCurNext = cur.next
oldCurNextNextNext = cur.next.next.next
cur.next = cur.next.next
cur.next.next = oldCurNext
oldCurNext.next = oldCurNextNextNext
cur =cur.next.next
return dummy.next
19.删除链表的倒数第N个节点
思路
两个人同样的速度匀速跑步，初始时B在A前面n米，此时两人同时跑步，则B到达终点时，A距离终点也是n米。类比删除倒数第n个的节点，需要slow和fast指针，fast先走n步，然后slow，fast同时走，则fast到达终点时，slow指向的就是倒数第n个节点。为了删除该节点，则应该找到待删除节点的前一个节点的引用，因此fast开始时先走n+1步，此时再按照刚才的逻辑，slow就会指向待删除节点的前一个节点，修改其指针域即可。此外，该题限制了n的正确性1 <= n <= size，因此不需要边界处理错误的情况。
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
slow,fast = dummy,dummy
while n:
fast=fast.next
n-=1
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。
思路
与上面删除倒数第n个节点有点类似，先分别遍历两个链表，得到长度差异delta，此时知道哪个链表长哪个链表短，或者相同，类似之前的逻辑，长的先跑delta步,此时两个一起跑，则第一次遇到时就是它们的相交节点，如果短链表都遍历完了还没有遇到，说明两个链表不相交。
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
cur = headA
delta = 0
while cur:
cur = cur.next
delta+=1
cur = headB
while cur:
cur = cur.next
delta-=1
longerListPointer = headA if delta >0 else headB
shorterListPointer = headA if longerListPointer==headB else headB
delta = abs(delta)
while delta:
longerListPointer = longerListPointer.next
delta-=1
while shorterListPointer:
if longerListPointer == shorterListPointer:
return longerListPointer
longerListPointer= longerListPointer.next
shorterListPointer = shorterListPointer.next
return None
142.环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路
- 快慢指针相遇判断是否有环（是否相遇，之所以有环时一定相遇是因为它们的速度差为1个单位，不会发生快指针跳过慢指针的情况）。
- 入口节点
- 方法一：相遇后，让其中一个节点从头走，然后另一个节点从当前位置走，再次相遇即是入口节点（需要画图用等式证明，不是很好想到，而且暂时没有理解为什么快指针追上慢指针至少需要一圈）
- 方法二：这个方法利用哈希表来存储已经访问过的节点，检测到第一个重复访问的节点即为环的入口节点。 （好理解，但空间复杂度O（n）)
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow,fast = head,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
总结
今天起的太早出门，状态很差，抽时间把今天的题再思考和做一下。今天主要学到的有以下几点。
- 链表中修改指针（插入，删除）类似题目的核心是，弄清楚一次循环中需要修改哪些指针域，以及修改顺序。快慢指针可以
- 快慢指针在链表中的应用，可以让快指针先走n步然后两个同时走，这里有个不变量就是它们的delta，此后当到达终点后，就有另一个等式，即终点离slow节点的距离就是n步
；另外，快慢指针还可以弥补两个不同相交链表的行走差距 - 快慢指针在环形链表入口节点的应用，后续需要思考下为什么fast指针至少跑一圈才能追上slow