代码随想录训练营 Day4打卡 链表part02
一、 力扣24.两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
算法思路：
-
引入虚拟头结点：创建一个虚拟头结点 dummyHead，它的 next 指向原始链表头，简化边界处理。
-
初始化指针：cur 初始化为 dummyHead，用于遍历链表。
-
交换节点：在链表中两两交换节点，直到链表尾部。
-
使用临时变量 tmp 和 tmp1 来辅助交换操作。
-
通过三步更新指针，完成相邻节点的交换。
-
返回结果：交换完成后，dummyHead->next 即为新链表头，返回之。
版本一：迭代实现
实现思路：
- 创建哑节点指向链表头，以处理头节点交换。
- 遍历链表，每次检查并交换成对的节点。
- 交换完成后，返回哑节点的下一个节点作为新的头节点。
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummy_head = ListNode(next=head)
current = dummy_head
# 必须有cur的下一个和下下个才能交换，否则说明已经交换结束了
while current.next and current.next.next:
temp = current.next # 保存当前节点的下一个节点
temp1 = current.next.next.next # 保存当前节点的下下个节点的下一个节点
current.next = current.next.next # 交换：current.next指向下下个节点
current.next.next = temp # 交换：新的current.next.next指向原来的current.next
temp.next = temp1 # 交换：原来的current.next.next指向temp1
current = current.next.next # 移动到下一对节点准备交换
return dummy_head.next
版本二：递归实现
实现思路：
- 递归终止条件为链表为空或只有一个节点。
- 交换当前的两个节点，并递归处理后续节点。
- 返回新的头节点。
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
# 待翻转的两个node分别是pre和cur
pre = head
cur = head.next
next = head.next.next
cur.next = pre # 交换：cur.next指向pre
pre.next = self.swapPairs(next) # 递归处理next作为新头节点的链表，并赋值给pre.next
return cur # 返回新的头节点cur
二、力扣19. 删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
算法思路
为了删除链表中倒数第N个节点，采用双指针法：
-
引入虚拟头结点：简化边界处理，使删除操作统一。
-
初始化双指针：fast 和 slow 均指向虚拟头结点。
-
fast 先行：fast 指针先移动N+1步，拉开与slow的距离。
-
同步移动：两指针同时前进，直至fast到达链表尾部。
-
删除节点：此时slow指向目标节点的前驱，可安全删除倒数第N个节点。
这种方法避免了多次遍历或额外数据结构的使用，提高了效率。
代码实现
# 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: ListNode, n: int) -> ListNode:
# 创建一个虚拟节点，并将其下一个指针设置为链表的头部
dummy_head = ListNode(0, head)
# 创建两个指针，慢指针和快指针，并将它们初始化为虚拟节点
slow = fast = dummy_head
# 快指针比慢指针快 n+1 步
for i in range(n+1):
fast = fast.next
# 移动两个指针，直到快速指针到达链表的末尾
while fast:
slow = slow.next
fast = fast.next
# 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点
slow.next = slow.next.next
return dummy_head.next
三、面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例一：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
算法思路（一）：
步骤1：确定链表长度差
首先，我们需要确定两个链表的长度差。为此，我们初始化两个指针 curA 和 curB 分别指向链表 A 和 B 的头节点。我们遍历这两个链表直到它们的末尾，同时计数每个链表的节点数量。这样我们就能知道链表 A 和 B 的长度。
步骤2：对齐较短的链表
一旦我们知道了两个链表的长度差，我们就可以将较长链表的指针向前移动这个差值，这样两个指针就会处于同一水平线上，即它们距离各自链表的末尾有相同的距离。
步骤3：同步移动并查找交点
接下来，我们同步移动 curA 和 curB。由于它们现在处于对齐状态，如果链表有交点，那么当 curA 和 curB 指向同一个节点时，我们就找到了交点。我们只需要遍历一次剩余的链表即可找到交点。
版本一：求长度，同时出发
实现思路：
- 分别计算链表A和链表B的长度。
- 通过移动较长链表的头，使得两个链表在同一起点开始遍历。
- 同时遍历两个链表，当遇到相同节点时返回该节点，否则返回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: # 遍历curA 和 curB，遇到相同则直接返回
if curA == curB:
return curA
else:
curA = curA.next
curB = curB.next
return None
版本二：求长度，同时出发（代码复用 + 精简）
实现思路：
- 计算两个链表长度的差值。
- 通过辅助方法moveForward移动较长链表的头节点，使两链表长度相等。
- 同时遍历两个链表，找到相交节点。
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
dis = self.getLength(headA) - self.getLength(headB)
# 通过移动较长的链表，使两链表长度相等
if dis > 0:
headA = self.moveForward(headA, dis)
else:
headB = self.moveForward(headB, abs(dis))
# 将两个头向前移动，直到它们相交
while headA and headB:
if headA == headB:
return headA
headA = headA.next
headB = headB.next
return None
def getLength(self, head: ListNode) -> int:
length = 0
while head:
length += 1
head = head.next
return length
def moveForward(self, head: ListNode, steps: int) -> ListNode:
while steps > 0:
head = head.next
steps -= 1
return head
算法思路（二）
假设有两个链表A和B，它们在某个节点处相交。链表A的长度为m，链表B的长度为n。假设相交节点之前，链表A有a个节点，链表B有b个节点，且相交部分长度为c。则有：
m=a+c
n=b+c
使用两个指针pointerA和pointerB分别遍历链表A和链表B。当一个指针到达链表末尾时，将其重定位到另一个链表的头部。这样做的目的是使两个指针在相同的步数之后都到达相交节点。
在这种遍历方式下，pointerA和pointerB在第二次遍历时会在相交节点相遇。
具体来说，当两个指针都遍历完各自的链表，并切换到对方的链表头部时，它们实际走过的节点数是相等的。
设pointerA和pointerB走的步数分别为L1和L2：
pointerA走的步数：a + c + b
pointerB走的步数：b + c + a
由于a + b + c是固定的，所以在相交点处两个指针会相遇。
版本三：等比例法
实现思路：
- 初始化两个指针，分别指向两个链表的头。
- 同时遍历两个链表，当一个指针到达链表末尾时，指向另一个链表的头。
- 当两个指针相等时，返回相交节点。
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# 处理边缘情况
if not headA or not headB:
return None
# 在每个链表的头部初始化两个指针
pointerA = headA
pointerB = headB
# 遍历两个链表直到指针相交
while pointerA != pointerB:
# 将指针向前移动一个节点
pointerA = pointerA.next if pointerA else headB
pointerB = pointerB.next if pointerB else headA
# 如果相交，指针将位于交点节点，如果没有交点，值为None
return pointerA
四、环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
算法思想
- 初始化：在链表中同时放置两个指针，slow 和 fast，均指向链表头部。
- 移动策略：slow 每次向前移动一个节点，而 fast 每次向前移动两个节点。
- 环检测：如果链表中存在环，由于 fast 移动速度是 slow 的两倍，它最终会追上 slow。如果两者相遇，则证明链表有环；如果
fast 达到链表尾部（即 fast 或 fast->next 是 nullptr），则表明链表无环。
为何会相遇？
这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。
如果有环，如何找到这个环的入口
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：
慢指针走过的节点数： x + y
快指针走过的节点数： x + y + n (y + z)
其中