4.3 双指针

双指针法解决链表问题有两种方式:

• 前后双指针: 一个指针提前向下个节点移动若干步, 然后再移动另一个指针 案例: 查找倒数第k个节点, 先让第一个指针移动k-1步, 之后和第二个(从头节点开始)一起移动. 当第一个指针到达尾节点时, 第二个指针刚好到达倒数第k个节点
• 快慢指针: 两个指针移动速度不同. 案例: 快指针一次移动两步, 慢指针一次移动一步; 当快指针到达末尾时, 慢指针指向中间节点.

4.3.1 问题21: 删除倒数第k个节点

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

给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

img

输入：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

**进阶：**能尝试使用一趟扫描实现吗？

4.3.1.1 分析

若要删除倒数第k个节点$n_k$ , 只需找到倒数第k+1个节点然后将其指针指向倒数第k-1个节点即可.

此时问题转化成了寻找倒数第k+1个节点, 使用前后双指针来解决:

1. 前指针从头节点开始, 先移动$(k+1)-1$即k步
2. 后指针和前指针开始同步移动, 直到前指针到达尾节点
3. 后指针指向倒数第k+1个节点, 将节点指针指向倒数第k-1个, 就删除了倒数第k个节点

只需遍历一次链表, 时间复杂度 O(n)

4.3.1.2 题解

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 哨兵节点, 免去单独判断删除头节点的情况
    dummy := &ListNode{}
    dummy.Next = head

    // 前后双指针
    front, back := head, dummy
    // 前指针移动 n 步
    for i := 0; i < n; i++ {
       front = front.Next
    }

    // 移动双指针
    for front != nil {
       front = front.Next
       back = back.Next
    }

    // 删除倒数第n个
    back.Next = back.Next.Next
    return dummy.Next
}

4.3.2 问题22: 链表中环的入口节点

LCR 022. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

**说明：**不允许修改给定的链表。

示例 1：

img

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

**进阶：**是否可以使用 O(1) 空间解决此题？

4.3.2.1 分析

使用快慢指针p1和p2:

1. p1 每次走两步, p2每次走一步
2. 若不存在环, 当p1走到尾节点时, 就会结束, 两者永远不会相遇
3. 若存在环, 但两者相遇时, p1 走了2k步, p2 走了 k 步; 而两者相遇的节点 p3 一定在环内; 又因为 p1 p2 的步数之差 k, 一定是 p1 在环内循环的步数, 所以 k 为环内节点的整数倍
4. 设定新指针 p4 从头节点开始, 然后 p3 和 p4 同步移动
5. 当 p3 和 p4 相遇时, 就是环的入口节点

4.3.2.2 题解

func detectCycle(head *ListNode) *ListNode {
	// 获取环中节点
	inLoop := getNodeInLoop(head)
	if inLoop == nil {
		return nil
	}

	// 前后指针
	front := head
	// 相遇点即为环入口
	for front != inLoop {
		front = front.Next
		inLoop = inLoop.Next
	}

	return front
}

func getNodeInLoop(head *ListNode) *ListNode {
	// 边界: 空链表或单节点
	if head == nil || head.Next == nil {
		return nil
	}

	// 快慢指针
	slow := head.Next
	fast := slow.Next // 步数为 slow 的两倍
	for fast != nil {
		// 相遇点
		if slow == fast {
			return slow
		}
		// slow 走一步
		slow = slow.Next
		// fast 走两步
		fast = fast.Next
		if fast != nil {
			fast = fast.Next
		}
	}

	return nil
}

4.3.3 问题23: 两个链表的第 i 个重合节点

LCR 023. 相交链表

给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交**：**

img

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

img

输入：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：

img

输入：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：

img

输入：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) 内存的解决方案？

4.3.3.1 分析

若使用暴力解法时间复杂度为 O($n^2$).

使用前后双指针的方式来解决:

1. 获取两个链表的长度差 d, O(m+n)
2. 前后双指针 f, b; 长链表的指针 f 先移动 d 步
3. f, b 同步移动, 那么相遇的节点就是重合节点

4.3.3.2 题解

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // 获取链表长度
    lenA := countList(headA)
    lenB := countList(headB)

    // 前后双指针
    longer, shorter := &ListNode{}, &ListNode{}
    delta := 0
    if lenA > lenB {
       longer = headA
       shorter = headB
       delta = lenA - lenB
    } else {
       longer = headB
       shorter = headA
       delta = lenB - lenA
    }

    // 先移动前指针
    for i := 0; i < delta; i++ {
       longer = longer.Next
    }
    // 同步移动
    for longer != shorter {
       longer = longer.Next
       shorter = shorter.Next
    }

    return longer
}

func countList(head *ListNode) int {
    count := 0
    for head != nil {
       head = head.Next
       count++
    }

    return count
}

Reference

1. 剑指Offer（专项突破版）