【算法刷题系列】第4天 24. 两两交换链表中的节点, 19. 删除链表的倒数第 N 个结点, 面试题 02.07. 链表相交, 142. 环形链表 II

calendar Aug 18, 2024 · 5 min read · algorithm 中文  ·
Share on: linkedin copy

Overview

收获总结

  1. 虚拟头节点的使用：虚拟头节点（Dummy Head）是处理链表问题的一大利器，尤其在增删节点操作中。通过引入虚拟头节点，可以避免处理链表头部时遇到的特殊情况，如删除第一个节点或在第一个节点前插入新节点。这不仅简化了代码，还减少了需要额外考虑的边界条件。例如，在处理 19. 删除链表的倒数第 N 个结点 时，虚拟头节点能够让双指针操作统一化，避免对头节点的单独处理。

  2. 双指针技术：双指针技术是链表问题中的核心工具，特别是在处理链表长度不一致、链表中查找特定节点、或检测链表是否存在环时。双指针通常有两种应用方式：

    • 快慢指针：通过让一个指针每次走两步（快指针），另一个指针每次走一步（慢指针），这种方法能有效检测链表中的环（如 142. 环形链表 II）。当快慢指针相遇时，表明链表中存在环。随后，通过调整指针，可以精确找到环的起点。
    • 同步指针：在链表相交问题中（如 面试题 02.07. 链表相交），同步指针的应用非常巧妙。让两个指针分别从两个链表的头开始遍历，当其中一个指针走到链表末尾时切换到另一个链表的头部，最终两个指针会在相交点相遇。这种方法的妙处在于，它平衡了链表长度的差异，使得指针在正确的位置相遇。

  3. 内置数据结构的应用：在处理链表问题时，合理使用内置的数据结构（如 map）可以大大提高解决问题的效率。例如，在检测链表是否有环时，使用哈希表可以记录已经访问过的节点，一旦再次访问到相同的节点，就可以立即判定链表中存在环，并找到环的入口。这种方法尽管增加了空间复杂度，但通常能够显著降低时间复杂度，是时间换空间的一种常见手段。

  4. 画图和理清思路：链表操作往往涉及多步节点指针的调整，容易出现操作顺序错误导致链表断裂或死循环的问题。因此，在进行复杂链表操作之前，通过画图来理清每一步的指针变动，明确节点间的连接关系，是非常必要的。比如在解决 24. 两两交换链表中的节点 问题时，通过画图可以清晰地看到每次交换后的链表结构，有助于正确实现节点交换。

  5. 操作的标准化和优化：在链表操作中，保持节点连接的正确性是最重要的。在实现代码时，应尽量避免无效或重复的操作。例如，在删除节点时，应确保先处理前驱节点的 next 指针，再释放目标节点的内存。同时，在实际开发中，掌握一些标准化的代码模板（如增删节点的通用代码框架）能够帮助减少错误，提高代码的复用性和开发效率。

题目解析

题目1：24. 两两交换链表中的节点

  • 题目描述: 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯地改变节点内部的值，而是需要实际进行节点交换。

  • 示例:

    1输入: head = [1,2,3,4]
2输出: [2,1,4,3]

  • 解法总结: 这个问题要求我们在链表中两两交换相邻的节点。为了简化操作，可以引入一个虚拟头节点（dummy head），它指向原链表的头节点，这样可以统一对头节点和后续节点的处理。然后使用双指针遍历链表，分别指向当前待交换的两个节点及其前驱节点。关键在于每次交换时，需要提前保存第二个节点的下一个节点，以防止链表断裂。假设1->2->3->4是待交换的两个节点，交换过程如下：

    1. 将pre指向2
    2. 将2指向1
    3. 将1指向3
    4. 将pre指向1
    5. 将cur指向3
    6. 重复上述步骤，直到cur或cur.Next为空

  • 代码实现:

     1/**
 2 * Definition for singly-linked list.
 3 * type ListNode struct {
 4 *     Val int
 5 *     Next *ListNode
 6 * }
 7 */
 8func swapPairs(head *ListNode) *ListNode {
 9	// 1. 加虚拟头，定义双指针
10	dummy := &ListNode{}
11	dummy.Next = head
12	cur := head
13	pre := dummy
14
15	// 2. 退出循环条件
16	for cur != nil && cur.Next != nil {
17		// 3. pre --> 2
18		pre.Next = cur.Next
19
20		// 4. 2 --> 1, 这里因为cur.Next.Next被改动了，所以要提前把原来的数据保存起来
21		tmp := cur.Next.Next
22		cur.Next.Next = cur
23
24		// 5. 1 --> 3
25		cur.Next = tmp
26
27		// 6. pre cur 指针移动
28		pre = cur
29		cur = tmp
30	}
31
32	return dummy.Next
33}

  • 时间复杂度: O(n)，因为我们需要遍历整个链表，n 是链表的长度。

  • 空间复杂度: O(1)，因为只使用了常量级别的额外空间。

题目2：19. 删除链表的倒数第 N 个结点

  • 题目描述: 给定一个链表，删除链表的倒数第 n 个节点，并返回链表的头节点。要求算法的时间复杂度为 O(n)。

  • 示例:

    1输入: head = [1,2,3,4,5], n = 2
2输出: [1,2,3,5]

  • 解法总结: 这道题的核心是如何在只遍历一次链表的情况下删除倒数第 n 个节点。使用双指针技术是一个非常有效的办法。通过让其中一个指针 fast 先前进 n 步，然后再让 fast 和另一个指针 slow 同时前进。当 fast 到达链表末尾时，slow 指针正好位于需要删除节点的前一个节点。这个过程只需要一次遍历，因而满足 O(n) 的时间复杂度要求。

    具体步骤:

    1. 初始化虚拟头节点和双指针:

      • 创建一个虚拟头节点 dummy，使 dummy.Next 指向 head，并初始化两个指针 fast 和 slow，均指向 dummy。

    2. 让 fast 先走 n 步:

      • 通过一个循环，让 fast 指针向前移动 n 步，这样 fast 和 slow 之间的距离正好是 n。

    3. 同时移动 fast 和 slow:

      • 当 fast 指向链表末尾（fast.Next 为 nil）时，slow 刚好指向需要删除节点的前一个节点。

    4. 删除节点:

      • 修改 slow.Next 指向 slow.Next.Next，从而删除目标节点。

    5. 返回结果:

      • 最终返回 dummy.Next 作为新的链表头。

    这种方法确保了在遍历链表一次的情况下，准确找到并删除倒数第 n 个节点。

  • 代码实现:

     1/**
 2 * Definition for singly-linked list.
 3 * type ListNode struct {
 4 *     Val int
 5 *     Next *ListNode
 6 * }
 7 */
 8func removeNthFromEnd(head *ListNode, n int) *ListNode {
 9	// 1. 定义双指针，增加dummy头
10	dummy := &ListNode{
11		Next: head,
12	}
13	fast := dummy
14	slow := dummy
15
16	// 2. 检查n的合法性
17	// 3. fast先走
18	for i := 0; i < n; i++ {
19		fast = fast.Next
20	}
21
22	// 4. fast和slow一起走，fast的下一个是nil的时候slow就到了该删除的值的前一位!
23	for fast.Next != nil {
24		fast = fast.Next
25		slow = slow.Next
26	}
27
28	slow.Next = slow.Next.Next
29	return dummy.Next
30}

  • 时间复杂度: O(n)，因为需要遍历链表一次，n 是链表的长度。

  • 空间复杂度: O(1)，因为只使用了常量级别的额外空间。

题目3：面试题 02.07. 链表相交

  • 题目描述: 给定两个单链表，找出它们相交的起始节点。如果两个链表没有交点，返回 null。

  • 示例:

    1输入: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]
2输出: Intersected at '8'

  • 代码实现:

  • 解法1: 该解法通过分别计算两个链表的长度，然后让较长的链表先行走差值步数，最后再同步遍历两个链表，以找到它们的相交节点。

    具体步骤:

    1. 计算两个链表的长度:

      • 分别遍历 headA 和 headB，计算出两个链表的长度 lengthA 和 lengthB。

    2. 对齐两个链表的起点:

      • 根据两个链表的长度差，调整较长链表的起始点，使两个链表在剩余长度上对齐。具体操作是让较长链表先走 |lengthA - lengthB| 步。

    3. 同步遍历两个链表:

      • 从新的起点开始，同时遍历两个链表，当 headA 与 headB 相等时，返回该节点，这个节点即为两个链表的相交节点。

    这种方法依赖于计算链表的长度，并通过调整起点来找到相交节点。

     1/**
 2 * Definition for singly-linked list.
 3 * type ListNode struct {
 4 *     Val int
 5 *     Next *ListNode
 6 * }
 7 */
 8func getIntersectionNode(headA, headB *ListNode) *ListNode {
 9	// 无增删改查操作可以不用虚拟头
10	// 1. 分别求出headA, headB的长度
11	tmpHeadA := headA
12	lengthA := 0
13	for tmpHeadA != nil {
14		tmpHeadA = tmpHeadA.Next
15		lengthA++
16	}
17
18	tmpHeadB := headB
19	lengthB := 0
20	for tmpHeadB != nil {
21		tmpHeadB = tmpHeadB.Next
22		lengthB++
23	}
24
25	// 2. 长的先走差值
26	if lengthA >= lengthB {
27		for i := 0; i < lengthA-lengthB; i++ {
28			headA = headA.Next
29		}
30	} else {
31		for i := 0; i < lengthB-lengthA; i++ {
32			headB = headB.Next
33		}
34	}
35
36	// 3. 一起走，看值是否相同，有的话就返回起始交点
37	for headA != headB {
38		headA = headA.Next
39		headB = headB.Next
40	}
41	return headA
42}
    • 时间复杂度: O(m + n)，其中 m 和 n 分别是两个链表的长度。
    • 空间复杂度: O(1)，只使用了常量级别的额外空间。

  • 解法2: 该解法通过双指针技术，让两个指针分别从 headA 和 headB 开始遍历，当遍历到链表末尾时，指针切换到另一个链表的起点。这样两个指针将在相交节点处相遇，或者在没有相交时，最终指向 null。

    具体步骤:

    1. 初始化双指针:

      • 初始化两个指针 i 和 j，分别指向 headA 和 headB。

    2. 遍历链表:

      • 在两个指针不相等的情况下，不断遍历链表。当一个指针到达链表末尾时，切换到另一个链表的头部继续遍历。最终两个指针要么在相交节点相遇，要么同时遍历完两个链表后都指向 null。

    这种方法不需要预先计算链表长度，通过双指针的遍历自然对齐并找到相交节点，代码更加简洁直观。

     1/**
 2 * Definition for singly-linked list.
 3 * type ListNode struct {
 4 *     Val int
 5 *     Next *ListNode
 6 * }
 7 */
 8func getIntersectionNode(headA, headB *ListNode) *ListNode {
 9	// 无增删改查操作可以不用虚拟头
10    // 直接开始走两个链表，判断是否相等，走完了就换到另一个
11    // 定义双指针
12    i := headA
13    j := headB
14
15    for i != j {
16        // if i.Next != nil不行，因为这样少判断了最后一位
17        if i != nil {
18            i = i.Next
19        } else {
20            i = headB
21        }
22
23        if j != nil {
24            j = j.Next
25        } else {
26            j = headA
27        } 
28    }
29
30    return i
31}
    • 时间复杂度: O(m + n)，其中 m 和 n 分别是两个链表的长度。
    • 空间复杂度: O(1)，只使用了常量级别的额外空间。

  • 对比:

    • 解法1：需要计算链表长度，并做一次长度调整后再同步遍历。逻辑上清晰，但步骤较多。
    • 解法2：使用双指针技术，不需要计算链表长度，通过自然对齐找到相交节点。代码更简洁高效，推荐使用。

题目4：142. 环形链表 II

  • 题目描述: 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

  • 示例:

    1输入: head = [3,2,0,-4], pos = 1
2输出: 返回索引为 1 的链表节点

  • 代码实现:

  • 解法1: 该解法使用哈希表记录访问过的节点，一旦再次访问到相同的节点，说明链表存在环，该节点即为环的起始节点。

    具体步骤:

    1. 定义哈希表:

      • 使用一个哈希表 map 来存储已经访问过的节点。

    2. 遍历链表:

      • 遍历链表，对于每个节点，检查它是否已经存在于哈希表中。如果存在，则说明该节点是环的起始节点，返回该节点。
      • 如果节点不在哈希表中，则将其加入哈希表，继续遍历。

    3. 返回结果:

      • 如果遍历完链表没有找到重复节点，说明链表无环，返回 null。

    这种方法直接有效，但需要额外的空间来存储已经访问过的节点。

     1/**
 2 * Definition for singly-linked list.
 3 * type ListNode struct {
 4 *     Val int
 5 *     Next *ListNode
 6 * }
 7 */
 8func detectCycle(head *ListNode) *ListNode {
 9	// 1. 定义map
10    meet := map[*ListNode]bool{}
11
12    // 2. 直接Next找，每次存到meet这个map里面，如果碰到相同的就返回
13    for head != nil {
14        if _, ok := meet[head]; ok {
15            return head
16        }
17        meet[head] = true
18        head = head.Next
19    }
20
21    // 3. 不存在
22    return nil
23}
    • 时间复杂度: O(n)，其中 n 是链表的长度。
    • 空间复杂度: O(n)，用于存储已经访问过的节点。

  • 解法2: 使用快慢指针技术，通过让快指针（一次走两步）和慢指针（一次走一步）同时遍历链表，若链表有环，则两个指针会在环内相遇。然后通过调整指针，找到环的起点。

    具体步骤:

    1. 初始化快慢指针:

      • 初始化快指针 fast 和慢指针 slow，都指向 head。

    2. 检测环:

      • 快指针每次走两步，慢指针每次走一步。如果快指针与慢指针在某一点相遇，说明链表中存在环。

    3. 找到环的起点:

      • 当快慢指针相遇时，将其中一个指针移到链表头部，然后两个指针每次都走一步。最终它们会在环的起始节点相遇。

    4. 返回结果:

      • 如果快慢指针相遇，返回该节点；如果快指针遍历完链表没有相遇，返回 null。

    这种方法不需要额外的存储空间，通过数学推导和遍历链表，能够在常数空间下检测环并找到环的起点。

     1/**
 2 * Definition for singly-linked list.
 3 * type ListNode struct {
 4 *     Val int
 5 *     Next *ListNode
 6 * }
 7 */
 8func detectCycle(head *ListNode) *ListNode {
 9	// 1. 定义快慢指针
10	slow := head
11	fast := head
12
13	// 2. slow前进步幅为1，fast前进步幅为2；fast按照永远领先一个逼近slow；如果有环在绕了n圈之后一定会相交!
14	for fast != nil && fast.Next != nil {
15		fast = fast.Next.Next
16		slow = slow.Next
17
18		if fast == slow {
19			for slow != head {
20				head = head.Next
21				slow = slow.Next
22			}
23			return head
24		}
25	}
26	return nil
27}
    • 时间复杂度: O(n)，其中 n 是链表的长度。
    • 空间复杂度: O(1)，只使用了常量级别的额外空间。

  • 对比:

    • 解法1：哈希表法直接而有效，但空间复杂度较高。
    • 解法2：快慢指针法通过数学推导实现，时间复杂度和空间复杂度都更优，在实际应用中更为推荐。