24. 两两交换链表中的节点
力扣题目链接(opens new window)
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
提示：
-
链表中节点的数目在范围 [0, 100] 内
-
0 <= Node.val <= 100
代码
这题的意思是如果cur与cur.next存在，就交换
需要注意的是next是个指针。
简单点看
temp1 = cur.next
temp2 = cur.next.next
temp3 = cur.next.next.next
cur.next = temp2
temp2 = temp1
temp1 = temp3
如此，简单来看
class ListNode:
def __init__(self, val=0, next=None):
# 初始化一个链表节点
self.val = val # 节点的值
self.next = next # 指向下一个节点的指针
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 创建一个虚拟头节点 dummy_head，它的 next 指向链表头
# 这样可以简化边界情况的处理
dummy_head = ListNode(0, head)
# 初始化当前节点 cur 为 dummy_head
cur = dummy_head
# 当 cur 的下一个节点和下下个节点都存在时，继续循环
while cur.next and cur.next.next:
# 临时保存 cur 的下一个节点（第一个节点）
temp1 = cur.next
# 临时保存 cur 的下下个节点（第二个节点）的下一个节点
temp3 = cur.next.next.next
# 将 cur 的 next 指向第二个节点
cur.next = cur.next.next
# 第二个节点的 next 指向第一个节点
cur.next.next = temp1
# 第一个节点的 next 指向第三个节点
temp1.next = temp3
# 移动 cur 到已经完成交换的节点对之后
cur = cur.next.next
# 返回新的链表头，即 dummy_head 的下一个节点
return dummy_head.next19.删除链表的倒数第N个节点
力扣题目链接(opens new window)
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
代码
一开始我想的也是递归，但我思路非常混乱。
我想着先用递归到底，到第底后再回到第n+1个进行删除。
我混乱的地方在于如何到底再统计回来的数，而且全放在一个函数，会导致返回的是count而不是列表
看了眼题解，使用的是函数嵌套，一个用来递归，一个用来给答案
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，它的 next 指向链表头
# 这样可以简化边界情况的处理，例如删除头节点
dummy_head = ListNode(-1, next=head)
# 定义一个递归函数来遍历链表并计算节点位置
def traversed(cur: ListNode, n: int) -> int:
# 如果当前节点为空，返回计数器为0
if cur is None:
return 0
# 递归调用自身，继续遍历下一个节点
count = traversed(cur.next, n) + 1
# 当递归回溯时，如果当前节点是目标节点（即倒数第 n+1 个节点）
if count == n + 1:
# 删除倒数第 n 个节点
cur.next = cur.next.next
# 返回当前节点的位置
return count
# 从虚拟头节点开始递归遍历
traversed(dummy_head, n)
# 返回新的链表头，即 dummy_head 的下一个节点
return dummy_head.next附上灵佬的代码
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# 由于可能会删除链表头部，用哨兵节点简化代码
left = right = dummy = ListNode(next=head)
for _ in range(n):
right = right.next # 右指针先向右走 n 步
while right.next: # 因为是right.next所以right前面不用再走一步。
left = left.next
right = right.next # 左右指针一起走
left.next = left.next.next # 左指针的下一个节点就是倒数第 n 个节点
return dummy.next面试题 02.07. 链表相交
同：160.链表相交
力扣题目链接(opens new window)
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：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 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '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 。
代码
第一种方法是长的先走，直到双方同样长，因为相交节点在后面，不会在头结点。
第二种办法是一起走，走到头就走另一边
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if headA is None or headB is None:
return None
pA, pB = headA, headB
while pA != pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
# if pA is not None:
# pA = pA.next
# else
# pA = headB
#算法逻辑
初始化：
p1 指向 headA，p2 指向 headB。
遍历和切换：
当 p1 和 p2 不相等时，进行以下操作：
如果 p1 到达 headA 的末尾（即 p1 == null），则将 p1 移动到 headB。
否则，p1 向前移动一步（即 p1 = p1.next）。
如果 p2 到达 headB 的末尾（即 p2 == null），则将 p2 移动到 headA。
否则，p2 向前移动一步（即 p2 = p2.next）。
返回结果：
当 p1 和 p2 相遇时，它们要么同时为 null（表示没有交点），要么都指向交点节点。
为什么会在交点处相遇？
假设两个链表 A 和 B 的长度分别为 lenA 和 lenB，并且它们在某个节点 C 处相交。从交点 C 到链表末尾的长度是 c。
如果 p1 和 p2 在各自的链表上前进，当 p1 到达 headA 的末尾时，它会跳转到 headB 继续前进。
同样，当 p2 到达 headB 的末尾时，它会跳转到 headA 继续前进。
这样，p1 和 p2 实际上走过的总距离是相同的：lenA + c 和 lenB + c。因此，无论 lenA 和 lenB 是否相等，p1 和 p2 最终都会在交点 C 或者同时到达 null（如果没有交点）。
具体例子
假设链表 A 和 B 的结构如下：
A: a1 -> a2 -> C -> c1 -> c2
B: b1 -> b2 -> b3 -> C -> c1 -> c2
其中，C 是交点节点。
p1 从 A 开始，走过 a1, a2, C, c1, c2，然后跳到 B，继续走过 b1, b2, b3。
p2 从 B 开始，走过 b1, b2, b3, C, c1, c2，然后跳到 A，继续走过 a1, a2。
最终，p1 和 p2 都会在 C 节点相遇，因为它们走过的总距离是相同的。
数学证明
设 lenA 为 A 的长度，lenB 为 B 的长度，c 为从交点 C 到链表末尾的长度。
p1 走的距离是 lenA + c。
p2 走的距离是 lenB + c。
由于 p1 和 p2 在各自链表上走完后会跳转到另一个链表，所以它们实际走过的总距离是相等的。因此，它们一定会在交点 C 相遇，或者同时到达 null（如果没有交点）。
这种设计使得即使两个链表长度不同，也能通过这种方式找到交点，而不需要额外的空间来存储链表的长度或其他信息。
142.环形链表II
力扣题目链接(opens new window)
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
-
链表中节点的数目范围在范围 [0, 104] 内
-
-105 <= Node.val <= 105
-
pos 的值为 -1 或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
代码
难点1：如何证明是否有环：
通过一个一次走一格的slow指针和一个一次走两格的fast指针（相对而言两者每次靠近一格，fast指针不会跳过slow指针。
两者必定会在环中一点相交。其中slow指针第一圈必定没走完。设环的长度为n，slow进圈时fast可能在环内任意一点，两者距离K一定小于n，而我们知道fast与slow一次靠近一格，因此必定在slow走完第一圈前相遇。
难点2：如何找到入环节点：
这里修改代码随想录的解释，写快一点
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)
两边消掉一个（x+y）: x + y = n (y + z) // y是入环节点到相遇节点顺时针的距离，z是相遇节点到入环节点顺时针的距离。
因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
所以要求x ，将x单独放在左面：x = n (y + z) - y ,
再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
在公式中，n(y+z)完全不重要，因为y+z即为一次完整的圈，即fast指针的位置不会因此改变。也就是说，在两者最后相遇的那圈中，fast与slow指针必定会走到入环节点（因为z是fast指针从相遇节点走到入环节点的距离）。区别只是两个指针兜兜转转在环里转了多少圈。
这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
# 初始化两个指针，slow 和 fast，都指向链表头部
slow = head
fast = head
# 使用快慢指针遍历链表
while fast and fast.next:
# 慢指针每次移动一步
slow = slow.next
# 快指针每次移动两步
fast = fast.next.next
# 如果在某个时刻慢指针和快指针相遇，则说明链表中存在环
if slow == fast:
# 一旦发现环，将慢指针移回链表头部
slow = head
# 然后让慢指针和快指针以相同速度前进，直到它们再次相遇
while slow != fast:
slow = slow.next
fast = fast.next
# 当慢指针和快指针再次相遇时，相遇点即为环的起始节点
return slow
# 如果快指针或其下一个节点变为 None，说明没有环
return None另外附上集合法方法，就是把链表节点当做集合元素，查找是否重复，重复的第一个单位就是入链结点
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
# 创建一个空集合来存储已经访问过的节点
visited = set()
# 遍历链表
while head:
# 如果当前节点已经在集合中，说明找到了环的入口
if head in visited:
return head # 返回当前节点（即环的起点）
# 将当前节点添加到已访问的集合中
visited.add(head)
# 移动到下一个节点
head = head.next
# 如果遍历完整个链表都没有找到环，则返回 None
return None总结
链表的理论基础
- 链表的种类主要为：单链表，双链表，循环链表
- 链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
- 链表是如何进行增删改查的。
- 数组和链表在不同场景下的性能分析。
虚拟头结点
链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。
每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。
链表的基本操作
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点的数值
反转链表
可以先通过迭代法，彻底弄清楚链表反转的过程！
删除倒数第N个节点
我们结合虚拟头结点 和 双指针法（快指针先走n步）来移除链表倒数第N个节点。
不过我用的是递归法，需要注意的是一个函数用于传递头节点，一个函数用于删除节点。
链表相交
使用双指针（长的链表，指针走到一样长）来找到两个链表的交点。（引用完全相同，即：内存地址完全相同的交点）
环形链表
重点在于在链表如何找环，以及如何找环的入口位置。
标签：head,cur,随想录,next,链表,节点,指针 From： https://blog.csdn.net/2401_87652382/article/details/142771624