19.删除链表的最后第N个节点141。环形链表142。环形链表II160。相交链表19。删除链表的最后第N个节点给定一个链表，删除链表的倒数第n个节点，并返回链表的头节点。示例：给定一个链表：1->2->3->4->5，且n=2。当删除倒数第二个节点时，链表变为1->2->3->5。说明：给定的n保证有效。Advanced：可以尝试使用one-passscan实现吗？思路是设置两个指针，第一个走n步，然后两个指针一起往前走。当第一个指针到达链表末尾时，第二个指针刚好指向倒数第n个元素defremoveNthFromEnd(head,n):ifn<1orhead==None:returnheadp_fast=p_slow=head#快指针向前移动n步foriinrange(n):p_fast=p_fast.next#如果此时fast指针为None，则要删除的节点为头节点ifp_fast==None:returnhead.next#Thefast和slow指针同时前进，而p_fast.next!=None:p_fast=p_fast.nextp_slow=p_slow.nextp_slow.next=p_slow.next.nextreturnhead的时间复杂度为$O(n)$，空间复杂度为$O(1)$141。循环链表给定一个链表，判断链表中是否存在环。为了表示给定列表中的循环，我们使用整数pos来表示列表中尾部连接的位置（索引从0开始）。如果pos为-1，则列表中没有循环。示例1：输入：head=[3,2,0,-4],pos=1输出：true解释：链表中有一个循环，其尾部连接到第二个节点。示例2：输入：head=[1,2],pos=0输出：true解释：链表中有一个循环，其尾部连接到第一个节点。示例3：输入：head=[1],pos=-1输出：false解释：链表中没有循环。更进一步：你能用O(1)（即常量）内存解决这个问题吗？一个直观的想法是用字典记录每个节点的访问状态，并返回FalsedefhasCycle(head):ifnothead:returnFalsedicts={}whilehead:ifheadindicts:returnTruedicts[head]=1head=head.nextreturnFalse时间复杂度$O(n)$，空间复杂度$O(n)$思路2，双指针设置两个速度不同的指针，分别为p1和p2，p1前进一步每次，p2每次前进2步。如果链表不包含环，那么p2会先到达尾部，此时返回False。如果链表包含一个环，那么p2将在最后追上p1。结束，返回TruedefhasCycle(head):if(nothead)or(nothead.next):returnFalsep1=headp2=head.nextwhilep1!=p2:p1=p1.nextifnotp2ornotp2.next:returnFalsep2=p2.next.nextreturnTrue时间复杂度$O(n)$，空间复杂度$O(1)$142。循环链表II给定一个链表，将链表的第一个条目返回到环a节点中。如果列表是非循环的，则返回null。为了表示给定列表中的循环，我们使用整数pos来表示列表中尾部连接的位置（索引从0开始）。如果pos为-1，则列表中没有循环。说明：不允许修改给定的链表。示例1：输入：head=[3,2,0,-4],pos=1输出：tail连接到节点索引1解释：链表中有一个循环，其尾部连接到第二个节点。示例2：输入：head=[1,2],pos=0输出：tail连接到节点索引0解释：链表中有一个循环，其尾部连接到第一个节点。示例3：输入：head=[1],pos=-1输出：nocycle解释：链表中没有环。高级：你能在没有额外空间的情况下解决这个问题吗？同上题一样，也可以用字典求解defdetectCycle(head):ifnotheadornothead.next:returnNonedicts={}p=headwhilep:ifpindicts:returnpelse:dicts[p]=0p=p.nextreturnNone时间复杂度为$O(n)$，空间复杂度为$O(n)$思路2如下图所示，最左边的红色节点代表起始链表的节点p_start，中间的红色节点代表循环链表的入口节点p_entrance，右边的红色节点代表快慢节点第一次相遇的节点p_inter。p_start和p_entrance之间的距离是F，p_entrance和p_inter之间的距离是a，p_inter和p_entrance之间的距离是b。快慢指针同时向前移动，在p_iter处相遇，则成立如下公式$2(F+a)=(F+a+b+a)+1$得到$F=b+1$defdetectCycle(head):ifnotheadornothead.next:returnNone#设置快慢指针，快指针从第二个节点开始fast=head.nextslow=head#has_cycle=inter_node=None#fastfastandfast.next:#当fast指针和slow指针指向同一个位置时，退出循环iffast==slow:inter_node=fastbreakfast=fast.next.nextslow=slow.next#比如如果inter_node为None，表示非循环ifnotinter_node:returnNonefast=headslow=inter_node.nextwhilefast!=slow:fast=fast.nextslow=slow.nextreturnslow总体思路是设置fast指针(每次2步）和慢指针（每次1步），同时开始，如果最后的快指针和慢指针指向同一个位置，说明有循环。将快指针向后移动一个节点，慢指针指向头节点，然后同时以的速度使用相同的Start。直到开会，回到开会节点。160.相交链表编写程序寻找两个单向链表相交的起始节点，例如下面的两个链表：开始相交于节点c1。示例1：输入：intersectVal=8,listA=[4,1,8,4,5]，listB=[5,0,1,8,4,5]，skipA=2，skipB=3输出：Referenceofvalue=8的节点输入说明：交集节点的值为8（注意如果两个链表相交则不能为0）。从各自的表头算起，链表A为[4,1,8,4,5]，链表B为[5,0,1,8,4,5]。A中，相交节点之前有2个节点；在B中，相交节点之前有3个节点。示例2：输入：intersectVal=2,listA=[0,9,1,2,4]，listB=[3,2,4]，skipA=3，skipB=1输出：值为2的节点的引用输入说明：交集节点的值为2（注意如果两个链表相交则不能为0）。从各自的表头算起，链表A为[0,9,1,2,4]，链表B为[3,2,4]。A中，相交节点之前有3个节点；在B中，相交节点之前有1个节点。示例3：输入：intersectVal=0,listA=[2,6,4],listB=[1,5],skipA=3,skipB=2输出：null输入解释：从每个表的表头开始计数，链表A是[2,6,4]，链表B是[1,5]。由于两个链表不相交，intersectVal必须为0，而skipA和skipB可以是任意值。解释：两个链表不相交，所以返回null。注意：如果两个链表没有交集，则返回null。返回结果后，两个链表必须仍然保持原来的结构。可以假设整个链表结构中没有环。该程序尽量满足O(n)的时间复杂度，只使用O(1)的内存。思路一：使用栈defgetIntersectionNode(headA:ListNode,headB:ListNode):ifnotheadAornotheadB:returnNonestacka=[]stackb=[]pa=headApb=headB#把链表a的所有节点入栈whilepa:stacka.append(pa)pa=pa.next#将链表b的所有节点压入栈whilepb:stackb.append(pb)pb=pb.nextres=Nonepa=stacka.pop()pb=stackb.pop()#一个一个弹出栈whilepa==pb:res=paifnotstackaornotstackb:breakpa=stacka.pop()pb=stackb.pop()returnres时间复杂度$O(m+n)$，空间复杂度$O(m+n)$思路二：使用字典defgetIntersectionNode(headA:ListNode,headB:ListNode):ifnotheadAornotheadB:returnNonedicts={}pa=headAwhilepa:dicts[pa]=1pa=pa.nextpb=headBwhilepb:#如果节点已经在字典中，可以直接returnifpbindicts:returnpbpb=pb.nextreturnNone时间复杂度为$O(m+n)$，空间复杂度为$O(m)$or$O(n)$思路3双指针设置指针p1，p2分别移动到headA和headB上如果p1指向None，将p1指向headB继续遍历如果p2指向None，则将p2指向headA继续遍历如果p1和p2指向的节点相同且不为None，则在遍历过程中找到相交节点过程中，两个指针为了保持相同的进度，消除了长度差异。当较长的链表指针指向较短的链表头时，长度差可以消除=p2:p1=headBifnotp1elsep1.nextp2=headAifnotp2elsep2.nextreturnp1的最后遍历次数为,时间复杂度为$O(m+n)$,空间复杂度is$O(1)$总结下面是关于快指针和慢指针的几个问题。快慢指针在链表中很常见，尤其是在遇到循环链表、交叉链表等问题时。快慢指针解决问题。他们的想法通常是利用路径差来得到关键节点的位置，从而解决问题。
