代码随想录算法训练营第四天|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II，总结
系列文章目录
代码随想录算法训练营第一天|数组理论基础，704. 二分查找，27. 移除元素
代码随想录算法训练营第二天|977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II
代码随想录算法训练营第三天|链表理论基础，203.移除链表元素，707.设计链表，206.反转链表
文章目录
- 系列文章目录
- 24. 两两交换链表中的节点
- 19.删除链表的倒数第N个节点
- 面试题 02.07. 链表相交
- 142.环形链表II
- 总结
24. 两两交换链表中的节点
题目链接： 24.两两交换链表中的节点
题目内容： 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
视频讲解：手把手带你学会操作链表 | LeetCode：203.移除链表元素
注意点： 1.最好设置一个虚拟节点方便操作；2.画图，不画图，操作多个指针很容易乱；3.要设置暂存节点，以防节点释放后找不到
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:dummyhead=ListNode(next=head)cur=dummyheadwhile cur.next is not None and cur.next.next is not None:#设置暂存节点指针temp1=cur.nexttemp2=cur.next.next.next#移动节点指针cur.next=cur.next.nextcur.next.next=temp1temp1.next=temp2#移动指针cur=cur.next.nextreturn dummyhead.next
19.删除链表的倒数第N个节点
题目链接： 19.删除链表的倒数第N个节点
题目内容： 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
视频讲解： 链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点
核心思想：如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummyhead=ListNode(next=head)fast=dummyheadslow=dummyheadwhile n and fast.next is not None: fast=fast.nextn-=1while fast.next is not None:fast=fast.nextslow=slow.nextslow.next=slow.next.nextreturn dummyhead.next
面试题 02.07. 链表相交
题目链接： 面试题 02.07. 链表相交
题目内容： 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
核心思想：求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:lenA,lenB=0,0#求链表A的长度cur=headAwhile cur:cur=cur.nextlenA+=1#求链表B的长度cur=headBwhile cur:cur=cur.nextlenB+=1curA,curB=headA,headB#使curB为最长链表的头，lenB为其长度if lenA > lenB:curA,curB=curB,curAlenA,lenB=lenB,lenA#让curA和curB在同一个起点上for _ in range(lenB-lenA):curB=curB.nextwhile curA:if curA==curB:return curAelse:curA=curA.nextcurB=curB.nextreturn None
142.环形链表II
题目链接： 142.环形链表
题目内容： 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。（不允许修改链表）
视频讲解： 把环形链表讲清楚！ 如何判断环形链表？如何找到环形链表的入口？
核心思路：使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:fast=headslow=headwhile fast is not None and fast.next is not None:fast=fast.next.nextslow=slow.nextif slow==fast:slow=headwhile slow!=fast:slow=slow.nextfast=fast.nextreturn slowreturn None总结
- 链表操作中一个非常重要的技巧：虚拟头节点。
链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。
- 双指针法可以解决大部分链表操作的题。