25-09-21 删除链表的倒数第 N 个结点 25-09-22 链表相交、环形链表 II 相关链接：代码随想录_链表

19. 删除链表的倒数第 N 个结点

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]

提示：

• 链表中结点的数目为 sz

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= 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. 链表相交

面试题 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 中节点数目为 m

• listB 中节点数目为 n

• 0 <= m, n <= 3 * 104

• 1 <= Node.val <= 105

• 0 <= skipA <= m

• 0 <= 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 可能会不相等吗

1. 同一类型的 nil 值是相等的

   var p1 *int = nil
   var p2 *int = nil
   fmt.Println(p1 == p2) // true

2. 不同类型的 nil 不能直接比较，编译会报错

   var p *int = nil
   var s []int = nil
   fmt.Println(p == s) // ❌ 编译错误：mismatched types *int and []int

3. 接口中存的 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

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 <= 105

• pos 的值为 -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) + z

n一定是大于等于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
}

总结