25-09-21 删除链表的倒数第 N 个结点
25-09-22 链表相交、环形链表 II
相关链接：代码随想录_链表
# 19. 删除链表的倒数第 N 个结点
中等
提示
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]示例 2：
输入：head = [1], n = 1 输出：[]示例 3：
输入：head = [1,2], n = 1 输出：[1]提示：
- 链表中结点的数目为
sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz进阶：你能尝试使用一趟扫描实现吗？
题目中标注了 1 <= n <= sz ，所以不用对n做不合法判断。
这道题适合用虚拟头结点，统一节点操作，不需要对头结点特殊处理。
# 快慢指针法
n 是要删除的倒数第 n 个节点
要求第 size-n 个节点，快指针先走 n ，然后快慢指针一起走。
则 快==慢+n 。当 快 == size 时，慢 == len - n （即要删除的节点）。
要处理某个节点，需要获取它前面的一个节点，那么我们应该找到 len-n 前面的一个节点。这时让快指针多走一步，那么 慢 == len-n-1。
func removeNthFromEnd(head *ListNode, n int) *ListNode {
DummyHead := &ListNode{Next: head}
fast, slow := DummyHead, DummyHead
// 要求删除第 size-n 个节点，快指针先走 n ，再快慢一起走，则 fast == slow + n;
// 当 fast == len 时， slow == size - n （需要删除的节点）
// 要删除某个节点，需要得到前一个节点，所以快指针多走一步(n+1)，slow == size - n - 1;
for i := 0; i < n + 1; i++ {
fast = fast.Next
}
for fast != nil { // fast == nil 时判断不通过，此时 fast 刚好走了 size 步
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return DummyHead.Next
}# 双循环法
先遍历链表获得 size，在遍历得到“前一个节点”，从而删除倒数第n个节点。
当时没想到用虚拟头结点，单独处理了头结点。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
var size int
cur := head
// 获取链表长度
for cur != nil {
size++
cur = cur.Next
}
if n == size {
return head.Next
} else {
cur = head
for i := 0; i < size - n - 1; i++ {
cur = cur.Next
}
cur.Next = cur.Next.Next
return head
}
}
# 面试题 02.07. 链表相交
简单
提示
给你两个单链表的头节点
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 。提示：
listA中节点数目为mlistB中节点数目为n0 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0- 如果
listA和listB有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]进阶：你能否设计一个时间复杂度
O(n)、仅用O(1)内存的解决方案？
# 思路
简单来说，就是求两个链表交点节点的指针。这里要注意，交点不是数值相等，而是指针相等。
为了方便举例，假设节点元素数值相等，则节点指针相等。
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
此时我们就可以比较 curA 和 curB 是否相同。
如果不相同： 同时向后移动 curA 和 curB；
如果相同： 则找到交点
否则退出循环，返回空指针。
func getIntersectionNode(headA, headB *ListNode) *ListNode {
// 分别遍历到最后一个节点，获取到链表长度
curA := headA
curB := headB
lenA, lenB := 0, 0
for curA != nil {
lenA++
curA = curA.Next
}
for curB != nil {
lenB++
curB = curB.Next
}
step := 0
var fast, slow *ListNode
if lenA > lenB {
step = lenA - lenB
fast, slow = headA, headB
} else {
step = lenB - lenA
fast, slow = headB, headA
}
// 先让 fast 走 step 步，将链表对齐
for i := 0; i < step; i++ {
fast = fast.Next
}
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return fast
}
# go 中两个 nil 可能会不相等吗
同一类型的 nil 值是相等的
var p1 *int = nil var p2 *int = nil fmt.Println(p1 == p2) // true不同类型的 nil 不能直接比较，编译会报错
var p *int = nil var s []int = nil fmt.Println(p == s) // ❌ 编译错误：mismatched types *int and []int接口中存的 nil 可能和直接的 nil 不相等
var x interface{} = nil var y interface{} = (*int)(nil) fmt.Println(x == nil) // true fmt.Println(y == nil) // false，因为 y 的动态类型是 *int，动态值是 nil
# 142. 环形链表 II
中等
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
示例 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 <= 105pos的值为-1或者链表中的一个有效索引进阶：你是否可以使用
O(1)空间解决此题？
# 快慢指针法
# 判断链表是否有环
可以用快慢指针法，分别定义 fast 和 slow 从头结点出发，fast 每次移动2个节点，slow 每次移动1个节点。如果 fast 和 slow 在途中相遇，说明这个链表有环。
为什么 fast 走2个节点， slow 走一个节点，有环的话，一定在环内相遇呢？
为什么 fast 走2个节点，slow 走一个节点，有环的话一定会在环内相遇呢，而不是永远的错开呢？
首先，fast 一定先进入环中，如果 fast 和 slow 相遇，一定是在环中相遇。（fast 转一圈和 slow 在入口也算在环中相遇）
为什么 fast 和 slow 一定会相遇呢？
相对与 slow 来说，fast 是一个节点一个节点地靠近 slow 的，所以 fast 一定可以和 slow 重合。
# 如果有环，如何找到这个环的入口
假设从头结点到环形入口节点的节点数为 x ；
从环形入口节点 到 fast 与 slow 相遇节点 的节点数为 y；
从相遇节点 再到 环形节点入口 的节点数为 z。如图所示：
那么相遇时，slow 走过的节点数为 x+y，fast 走过的节点数为 x+y + n(y+z) ， n 为 fast 在环内走了 n 圈才遇到 slow，(y+z) 为一圈内节点的个数。
因为 fast 一次走2个节点，slow 一次走1个节点。
slow走过的节点数 *2 == fast; 即：
(x + y)*2 == x+y + n*(y+z)
两边消掉1个(x+y)
x + y == n*(y+z)
需要求的是x
x == n*(y+z) - y
再提出一个 (y+z)
x == (n-1)*(y+z) + zn一定是大于等于1的，因为 fast 一定要多走一圈才能遇到 slow 。
x == (n-1)*(y+z) + z
当 n == 1 时（fast 多走1圈遇到 slow），x == z。这意味着：
从头结点出发一个指针，同时从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个节点相遇时就找到了环形入口的节点
当 n > 1 时，就是 fast 在环形转n圈后才遇到的 slow 指针，然后两个 index 开始走，和 n == 1 的情况效果是一样的。
详细代码：
func detectCycle(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
// 因为下一行要保证 fast.Next 不是空指针，从而也需要保证 fast 不是空指针
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
for slow != head {
slow = slow.Next
head = head.Next
}
return head
}
}
return nil
}
# 哈希表
遍历链表时，把遍历到的节点存进 map 中。
每次遍历节点时，查询下个节点是否在 map 中，如果在说明就找到了环入口。
func detectCycle(head *ListNode) *ListNode {
existNodes := make(map[*ListNode]int)
index := 0
cur := head
for cur != nil {
existNodes[cur] = index
index++
cur = cur.Next
for node, _ := range existNodes {
if cur == node {// 找到了入口
return cur
}
}
}
return nil
}# 总结
