二、链表刷题

1
移除链表元素
题目链接/文章讲解/视频讲解

defremoveElements(self,head:Optional[ListNode],val:int)->Optional[ListNode]:dummyNode=ListNode(next=head)cur=dummyNodewhilecur.next:ifcur.next.val==val:cur.next=cur.next.nextelse:cur=cur.nextreturndummyNode.next

2设计链表
文章讲解

classListNode:def__init__(self,val=0,next=None):self.val=val self.next=nextclassMyLinkedList:def__init__(self):self.dummy_head=ListNode()self.size=0defget(self,index:int)->int:ifindex<0orindex>=self.size:return-1current=self.dummy_head.nextforiinrange(index):current=current.nextreturncurrent.valdefaddAtHead(self,val:int)->None:self.dummy_head.next=ListNode(val,self.dummy_head.next)self.size+=1defaddAtTail(self,val:int)->None:current=self.dummy_headwhilecurrent.next:current=current.nextcurrent.next=ListNode(val)self.size+=1defaddAtIndex(self,index:int,val:int)->None:ifindex<0orindex>self.size:returncurrent=self.dummy_headforiinrange(index):current=current.nextcurrent.next=ListNode(val,current.next)self.size+=1defdeleteAtIndex(self,index:int)->None:ifindex<0orindex>=self.size:returncurrent=self.dummy_headforiinrange(index):current=current.nextcurrent.next=current.next.nextself.size-=1

3.反转链表
文章讲解

defreverseList(self,head:ListNode)->ListNode:cur=head pre=Nonewhilecur:temp=cur.nextcur.next=pre pre=cur cur=tempreturnpre

4.两两交换链表中的节点
文章讲解

defswapPairs(self,head:Optional[ListNode])->Optional[ListNode]:dummyNode=ListNode(0,head)nodeOne=dummyNode nodeTwo=headwhilenodeTwoandnodeTwo.next:#一定要两个条件，否则会报错temp=nodeTwo.next.nextnodeOne.next=nodeTwo.nextnodeTwo.next.next=nodeTwo nodeTwo.next=temp nodeOne=nodeTwo nodeTwo=temp# nodethree = nodeTwo.next #nodeTwo为0时会报错，所以不要初始化，可以直接用。returndummyNode.next

5.删除链表的倒数第N个节点
文章讲解

dummyNode=ListNode(0,head)cur=dummyNode pre=dummyNodeforiinrange(n):pre=pre.nextwhilepre.next:cur=cur.nextpre=pre.nextcur.next=cur.next.nextreturndummyNode.next

6.链表相交
文章讲解

lenA=1lenB=1cur=headAwhilecur:cur=cur.nextlenA+=1cur=headBwhilecur:cur=cur.nextlenB+=1iflenA<lenB:# 让curB为最长链表的头，lenB为其长度headA,headB=headB,headA lenA,lenB=lenB,lenAforiinrange(lenA-lenB):headA=headA.nextwhileheadA:ifheadA==headB:returnheadA headA=headA.nextheadB=headB.nextreturnNone

7.环形链表II
文章讲解

defdetectCycle(self,head:Optional[ListNode])->Optional[ListNode]:fast=slow=headwhilefastandfast.next:fast=fast.next.nextslow=slow.nextiffast==slow:slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone