Ⅱ 链表 episode3
接着上篇《Ⅱ 链表 episode2》, 完成链表类型的最后刷题。一点点小浪漫，表白Python，我爱它：）【买到了心爱小侯礼盒，美滋滋，要一直热爱下去】
思考总结
刷题学习过程关于链表的一些题型，我还是会纠结什么时候使用头结点（虚拟结点）？初始化指针究竟是位于头结点还是头结点.next（即head)？
我想这样是合理的（欢迎大家评论补充）：
头结点（虚拟结点）：简化链表的插入、删除逻辑，尤其是头部操作。比如插入删除首元素，就得分来讨论，引入虚拟结点的话，只需要一个while循环! 让逻辑看起来优雅简洁
# 不使用dummy(删除链表中为val的节点）
while head and head.val == val:head = head.nextcur = head
while cur and cur.next:if cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.next
# 使用dummy的话dummy = ListNode(-1)
dummy.next = head
cur = dummy
while cur.next:if cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.next
return dummy.next
初始化指针究竟是位于头结点还是头结点.next？
！！！取决于操作目标，是当前节点还是当前节点之后的，
-
指针指向虚拟头结点（dummy）：
-
需要修改链表结构、插入/删除节点等操作。
-
常常会改
cur.next，所以初始化为dummy是合适的。
-
-
指针指向真实头节点（head）：
-
如果只是遍历链表，或者对
head节点没有特殊修改的需求。
-
Gpt老师总结表格熟记于心
leetcode 19 删除链表倒数第N个节点
(呼应上面的思考，删除节点，dummy, 初始化在dummy处）
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def removeNthFromEnd(self, head, n):""":type head: Optional[ListNode]:type n: int:rtype: Optional[ListNode]"""# 设置虚拟节点dummy,dummy.next指向首节点dummy = ListNode(0,head)# 设定两个指针，一快一慢，fast先走n + 1步，这样同时移动的时候slow才能指向删除节点的上一个节点, 初始位于虚拟节点处# 结束条件，fast和slow同时移动，fast移动到null结束fast = slow = dummyfor i in range(n+1):fast = fast.nextwhile fast:fast = fast.nextslow = slow.nextslow.next = slow.next.next #删除操作return dummy.nextleetcode 160 相交链表
(呼应上面的思考，相交结点，只是遍历关系，不需要dummy, 初始化在head处）
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""# 仅遍历两链表，初始化指针在首节点处currentA = headAcurrentB = headB# 求两个链表的长度，然后让长链表先移动到，和短链长度首节点位置# 接着比较curA和curB是否相同，相同返回，不相同一起右移lenA, lenB = 0, 0while currentA:currentA = currentA.nextlenA += 1while currentB:currentB = currentB.nextlenB += 1# 此时currentA/B都在各自链表最后元素，通通放回初始点currentA = headAcurrentB = headB# 不确定俩链表谁长谁短，直接统一处理，总有个for循环不执行（负区间）for i in range(lenA-lenB): # 假如A长于BcurrentA = currentA.nextfor i in range(lenB-lenA): # 假如B长于AcurrentB = currentB.next# 开始比较了！一方为空指针就中止while currentA and currentB and currentA != currentB:currentA = currentA.nextcurrentB = currentB.nextreturn currentAleetcode 142 环形链表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: ListNode"""# 遍历链表，指针指向头结点就对了，不需要虚拟结点# 思路：快慢指针， fast 一次走两步，slow 一次走一步；链表环前有 L 个节点，环有C个节点（假设L<=C)# 快慢指针的相遇必在环内（无环不相遇，有环快追慢）# 当慢指针首次到达环入口时，快指针比它多走L，即快指针需再多走C-L才能相遇； # 由于v(快)-v(慢)=1，故相遇时慢指针又走了C-L，此时它与环起点距离为C-(C-L)=L；# 对于L>C的情况,可看作先将L不断减去C直到L<=Cfast, slow = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.next # 走两步if slow == fast: # 两指针相遇res = head # 初始化链表入环的第一个节点，放置首结点；若本身是环链表，res就是headwhile slow != res: # 当相遇点不是head时，让slow走L长度res = res.nextslow = slow.nextreturn resreturn None # 无环返回None
自主练习leetcode 140