24. 两两交换链表中的节点
题目连接：
24. 两两交换链表中的节点 - 力扣（Leetcode）
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
收获的点：
1）虚拟头节点应用理解的加深,返回链表只需要返回虚拟头节点的next即是完整链表
2）注意while循环的判断条件，因为同时更新两个节点的所以要cur.next和cur.next.next都不为空的条件下
完整代码
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummyhead = ListNode(next= head)
cur = dummyhead
while cur.next and cur.next.next:
tmp = cur.next #先把节点1保留
tmp1 = cur.next.next.next #保留节点3
#将虚拟头节点指向节点2
cur.next = cur.next.next #节点2去到了节点1的位置
cur.next.next = tmp #节点1去到了原先节点2的位置
cur.next.next.next = tmp1 #连接节点1->3
cur = cur.next.next #移动两个位置
return dummyhead.next
19.删除链表的倒数第N个节点
题目连接：
19. 删除链表的倒数第 N 个结点 - 力扣（Leetcode）
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
收获的点：
当时只想到倒数第n个数，就是正着数：链表的长度-n+1个数。当时没有想到用双指针。
解题的思路：双指针，让快指针先走到第n个节点，慢指针再走，当快指针走完了（遍历完链表的长度），慢指针实际上就是走了链表的长度-n个节点，然后慢指针=慢指针next 就是指向倒数第n个节点。
完整代码：
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummyhead = ListNode()
dummyhead.next = head
fast,slow= dummyhead,dummyhead
for _ in range(n):
fast = fast.next
while fast.next != None:
slow = slow.next
fast= fast.next
slow.next = slow.next.next
return dummyhead.next
面试题 02.07. 链表相交
题目链接：
面试题 02.07. 链表相交 - 力扣（Leetcode）
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
收获的点：
没有很理解（maybe是没有视频讲解），但是学到了获取链表长度的方法，就是相当于在循环里面放一个计数器。
完整代码：
solution1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
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:
if curA == curB:
return curA
else:
curA = curA.next
curB = curB.next
return None
solution2:
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
A,B = headA,headB
while A != B :
A = A.next if A else headB
B = B.next if B else headB
return A
142.环形链表II
题目链接：
142. 环形链表 II - 力扣（Leetcode）
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
收获的点：
1）想清楚数学逻辑很重要，比如相遇一定在环里面，相遇的点到环入口的距离与链表head到环入口的距离实际上是相等（解题的关键）。这样的题感觉好有趣，只是我还没这个高度:=||。
完整代码：
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast,slot = head,head
while fast and fast.next:
fast = fast.next.next
slot = slot.next
if fast == slot: #快慢指针相遇
index1 = head
index2 = slot
while index1!=index2:#直到两个指针相遇，相遇节点到环的入口的长度等于慢指针到环节点入口的长度，即视频中的x=z
index1 = index1.next
index2 = index2.next
return index1 #或者返回index2
return None
