剑指offer

剑指 offer 算法刷题记录（Golang 版）

链表

从尾到头打印链表

描述

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入{1,2,3}的链表如下图:

img

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func printListFromTailToHead(head *ListNode) []int {
	var stack []int
    var res []int
	for head != nil {
		stack=append(stack, head.Val)
        head = head.Next
	}
    for len(stack)>0{
        res = append(res, stack[len(stack)-1])
        stack = stack[:len(stack)-1]
    }
    return res
}

思路解释：

从尾到头的顺序，很容易想到栈的结构，后进先出即可。具体步骤如下：

  1. 初始化一个空的栈 stack 和结果数组 res。
  2. 遍历链表，将每个节点的值压入栈中。
  3. 遍历栈，将栈顶元素弹出并添加到结果数组中，直到栈为空。
  4. 返回结果数组 res。

这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是链表的长度。

好的，下面是对你提供的链表反转问题的总结：

链表反转

题目

给定一个单链表的头节点，反转该链表，并返回反转后的链表的头节点。

示例：

  • 输入：{1, 2, 3}
  • 输出：{3, 2, 1}

思路

链表反转的思路可以用一个非常经典的比喻来理解：想象你有一堆牌，你需要把它们的顺序颠倒过来。

  1. 三个指针： 我们需要三个指针来完成这个任务：

    • prev：指向已经反转好的链表的头节点。初始时，它指向 nil，因为最开始还没有反转任何节点。
    • current：指向当前正在处理的节点。
    • next：指向 current 节点的下一个节点，用于在断开 current 节点的 Next 指针之前，保存后续节点的引用，防止链表断裂。

  2. 迭代反转： 遍历链表，对于每个 current 节点，执行以下操作：

    • 保存 next： 首先，用 next 指针保存 current.Next，因为接下来要修改 current.Next。
    • 反转指针： 将 current.Next 指向 prev，实现反转。
    • 移动指针： 将 prev 移动到 current，current 移动到 next，为处理下一个节点做准备。

  3. 新的头节点： 当 current 指针到达链表末尾（nil）时，prev 指针指向的就是反转后链表的头节点。

图解：

假设链表为 1 -> 2 -> 3 -> nil

  1. 初始状态：
1
2
3
prev = nil
current = 1
next = 2
  1. 第一次迭代：
1
2
3
4
next = current.Next  // next = 2
current.Next = prev  // 1 -> nil
prev = current       // prev = 1
current = next       // current = 2

链表变为：1 <- 2 -> 3 -> nil (1 指向 nil)

  1. 第二次迭代：
1
2
3
4
next = current.Next  // next = 3
current.Next = prev  // 2 -> 1
prev = current       // prev = 2
current = next       // current = 3

链表变为：1 <- 2 <- 3 -> nil (2 指向 1)

  1. 第三次迭代：
1
2
3
4
next = current.Next  // next = nil
current.Next = prev  // 3 -> 2
prev = current       // prev = 3
current = next       // current = nil

链表变为：1 <- 2 <- 3 (3 指向 2)

  1. 循环结束：current 为 nil，prev 指向新的头节点 3。

算法代码 (Go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package main

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

func ReverseList(head *ListNode) *ListNode {
	// write code here
	var prev *ListNode = nil
	var current *ListNode = head
	for current != nil {
		next := current.Next // 保存下一个节点
		current.Next = prev  // 反转指针
		prev = current       // 移动 prev 指针
		current = next       // 移动 current 指针
	}
	return prev // prev 指向新的头节点
}

总结

  • 适用场景： 这种反转链表的方法适用于单链表结构。它是一种原地反转算法，只需要常数级别的额外空间（三个指针），因此空间复杂度为 O(1)。时间复杂度为 O(n)，因为需要遍历链表一次。
  • 算法类型： 链表操作
  • 技巧： 使用多个指针来辅助完成链表结构的修改是非常常见的技巧。一定要理清指针的指向关系，防止链表断裂。
  • 易错点： 在反转指针之前，一定要先保存下一个节点的引用，否则链表会断裂。
  • 变体： 链表反转有很多变体，例如反转链表的一部分（指定起始和结束位置）。基本思路都是类似的，需要仔细处理指针的指向。

好的，下面是对你提供的题目和代码的总结：

合并两个排序的链表

题目描述

输入两个递增的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围：

  • 单个链表的长度 n 满足 0 <= n <= 1000
  • 节点值满足 -1000 <= 节点值 <= 1000

要求：

  • 空间复杂度 O(1)
  • 时间复杂度 O(n)

解题思路

这道题的解题思路非常经典，就是迭代比较两个链表的当前节点，将较小的节点添加到新的链表中。 由于输入链表是递增的，所以我们只需要比较两个链表的头节点，将较小的节点作为新链表的头节点，然后递归地处理剩余的链表即可。

具体步骤如下：

  1. 初始化：

    • 创建一个哑节点（dummy node），作为合并后链表的头节点。哑节点不存储实际数据，只是为了方便操作。
    • 创建一个指针 current，指向哑节点，用于构建合并后的链表。

  2. 迭代比较：

    • 循环比较 pHead1 和 pHead2 指向的节点的值，直到其中一个链表为空。
    • 如果 pHead1.Val <= pHead2.Val，则将 pHead1 指向的节点添加到 current 的 Next 指针，并将 pHead1 向后移动一位。
    • 否则，将 pHead2 指向的节点添加到 current 的 Next 指针，并将 pHead2 向后移动一位。
    • 将 current 指针向后移动一位。

  3. 处理剩余节点：

    • 当其中一个链表为空时，将另一个链表剩余的节点直接添加到 current 的 Next 指针。

  4. 返回结果：

    • 返回哑节点的 Next 指针，即合并后的链表的头节点。

为什么使用哑节点？

使用哑节点可以避免对头节点的特殊处理，使代码更加简洁。如果没有哑节点，我们需要判断合并后的链表的头节点是 pHead1 还是 pHead2，这会增加代码的复杂性。

代码实现 (Go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package main

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
func Merge(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
	dummy := &ListNode{} // 创建哑节点
	current := dummy     // current 指针指向哑节点

	// 循环比较两个链表的节点
	for pHead1 != nil && pHead2 != nil {
		if pHead1.Val <= pHead2.Val {
			current.Next = pHead1 // 将 pHead1 的节点添加到新链表
			pHead1 = pHead1.Next    // pHead1 向后移动
		} else {
			current.Next = pHead2 // 将 pHead2 的节点添加到新链表
			pHead2 = pHead2.Next    // pHead2 向后移动
		}
		current = current.Next // current 向后移动
	}

	// 处理剩余节点
	if pHead1 != nil {
		current.Next = pHead1 // 将 pHead1 剩余的节点添加到新链表
	}
	if pHead2 != nil {
		current.Next = pHead2 // 将 pHead2 剩余的节点添加到新链表
	}

	return dummy.Next // 返回新链表的头节点
}

复杂度分析

  • 时间复杂度： O(n)，其中 n 是两个链表的总长度。我们需要遍历两个链表的所有节点。
  • 空间复杂度： O(1)。我们只使用了常量级的额外空间，例如哑节点和 current 指针。

适用题目类型

这种合并排序链表的思路，通常适用于以下类型的题目：

  • 涉及到两个或多个有序数据结构的合并问题。 例如，合并 k 个排序链表。
  • 需要保持合并后的数据结构仍然有序的问题。
  • 对空间复杂度有要求的题目。 由于该算法的空间复杂度为 O(1)，因此非常适合对空间复杂度有严格限制的题目。

举例：

  • LeetCode 23. 合并 K 个排序链表
  • 类似本题的变种，例如要求合并后链表为降序排列。

好的，我们来一起梳理一下这道寻找链表公共节点的题目。我会用易懂的方式解释思路，并提供带有详细注释的 Golang 代码。

寻找链表的第一个公共节点

题目描述：

给定两个无环的单向链表，找到它们的第一个公共节点。如果不存在公共节点，则返回 nil。

要求：

  • 空间复杂度为 O(1)。
  • 时间复杂度为 O(n)。

思路解析

想象一下，你在两条不同的河流上划船。两条河流最终汇入同一条河流，那么汇入点就是它们的第一个公共点。

  1. 长度差： 首先，我们需要知道两条河流（链表）的长度差。如果一条河流比另一条长，我们需要让较长的河流先划一段时间，直到它们到达同一起跑线。
  2. 同步前进： 然后，两条河流同时开始划船，每次都前进一步。当两条船在同一个位置时，我们就找到了它们的第一个公共点。
  3. 没有公共点： 如果两条河流一直没有相遇，那么它们就没有公共点。

图解：

假设我们有两个链表：

  • 链表 A: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
  • 链表 B: a -> b -> 4 -> 5 -> 6 -> 7

它们的第一个公共节点是 4。

用 Mermaid 图表示如下：

graph LR
    A1(1) --> A2(2)
    A2 --> A3(3)
    A3 --> A4(4)
    A4 --> A5(5)
    A5 --> A6(6)
    A6 --> A7(7)

    B1(a) --> B2(b)
    B2 --> A4

步骤：

  1. 计算链表 A 的长度（lenA = 7）。
  2. 计算链表 B 的长度（lenB = 2 + 5 = 7）。
  3. 计算长度差（diff = lenA - lenB = 0）。
  4. 因为长度相等，所以不需要移动任何链表的头指针。
  5. 同时遍历链表 A 和链表 B，直到找到相同的节点（即节点 4）。

Golang 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package main

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
func FindFirstCommonNode(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
	// 1. 判空处理：如果任一链表为空，则没有公共节点
	if pHead1 == nil || pHead2 == nil {
		return nil
	}

	// 2. 获取两个链表的长度
	len1 := GetLength(pHead1)
	len2 := GetLength(pHead2)

	// 3. 计算长度差，让较长的链表先走几步
	diff := 0
	if len1 > len2 {
		diff = len1 - len2
		for i := 0; i < diff; i++ {
			pHead1 = pHead1.Next // 移动 pHead1 到同一起跑线
		}
	} else {
		diff = len2 - len1
		for i := 0; i < diff; i++ {
			pHead2 = pHead2.Next // 移动 pHead2 到同一起跑线
		}
	}

	// 4. 同时遍历两个链表，查找相同节点
	for pHead1 != nil && pHead2 != nil {
		if pHead1 == pHead2 { // 直接比较指针，如果指针相同则找到公共节点
			return pHead1
		}
		pHead1 = pHead1.Next // 同时移动 pHead1
		pHead2 = pHead2.Next // 同时移动 pHead2
	}

	// 5. 如果没有找到公共节点，则返回 nil
	return nil
}

// GetLength 获取链表的长度
func GetLength(head *ListNode) int {
	length := 0
	for head != nil {
		length++        // 累加长度
		head = head.Next // 移动到下一个节点
	}
	return length
}

代码解释

  1. 判空处理： 如果任何一个链表为空，那么它们不可能有公共节点，直接返回 nil。
  2. 获取链表长度： GetLength 函数用于计算链表的长度。
  3. 调整起始位置： 计算长度差，并让较长的链表先移动，直到两个链表在同一起跑线上。
  4. 同步遍历： 同时遍历两个链表，比较节点是否相同。如果找到相同的节点，则返回该节点。
  5. 没有公共节点： 如果遍历完整个链表都没有找到公共节点，则返回 nil。

适用场景

这种方法特别适用于以下场景：

  • 寻找两个单链表的第一个公共节点。
  • 要求时间复杂度为 O(n)，空间复杂度为 O(1)。
  • 链表没有环。
#algorithm
剑指offer
https://mfzzf.github.io/2025/03/14/剑指offer/
作者
Mzzf
发布于
2025年3月14日
许可协议