Blog of AgioPan
0%

数据结构与算法自学笔记（12）- 链表高频题目和必备技巧

Posted on In ,

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记总结了链表类题目的高频考点和必备技巧，包含6道经典链表题目的详细解析。链表题目主要考察的是编程能力而非算法设计，是class034的内容。

前置知识

在学习链表高频题目之前，需要掌握以下基础知识：

  • 链表入门内容（009~012讲）
  • 归并排序（021讲）
  • 哈希表的使用（026讲）
  • 排序算法的稳定性（029讲）

链表定义

1
2
3
4
5
# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 节点存储的值
        self.next = next  # 指向下一个节点的指针

034【必备】链表高频题目和必备技巧

链表题目解题要点

核心注意事项

  1. 空间复杂度的选择：

    • 如果笔试中空间要求不严格，直接使用容器来解决链表问题
    • 如果笔试中空间要求严格、或者在面试中面试官强调空间的优化，需要使用额外空间复杂度O(1)的方法

  2. 最常用的技巧：快慢指针

  3. 考察重点：链表类题目往往都是很简单的算法问题，核心考察点并不是算法设计，而是coding能力

  4. 练习建议：既然练的就是coding，那么不要采取空间上讨巧的方式来练习（容器方法），这些题难就难在要用有限几个变量来解决

题目一：返回两个无环链表相交的第一个节点

问题描述

给定两个单链表的头节点，判断两个链表是否相交，如果相交返回第一个交点，否则返回None。

测试链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/

链表相交的概念

解题思路

容器解法（空间复杂度O(N)）：

  1. 遍历链表1，将每个节点加入哈希表
  2. 遍历链表2，检查每个节点是否在哈希表中
  3. 如果找到第一个在哈希表中的节点，即为第一个交点

最优解法（空间复杂度O(1)）：
核心思想是先判断两条链表是否相交，再找交点。

判断相交的关键：两条链表如果相交，最后一个节点一定是同一个节点（因为链表每个节点只有一个next指针）。

算法步骤

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
# 返回两个无环链表相交的第一个节点
def getIntersectionNode(self, h1: ListNode, h2: ListNode) -> ListNode:
    if not h1 or not h2:  # 任一链表为空，不可能相交
        return None

    a = h1  # a指针遍历链表1
    b = h2  # b指针遍历链表2
    diff = 0  # 记录两个链表的长度差
    
    # 遍历链表1，计算其长度
    while a.next:
        a = a.next  # a指针后移
        diff += 1  # 长度差加1

    # 遍历链表2，计算其长度
    while b.next:
        b = b.next  # b指针后移
        diff -= 1  # 长度差减1
    
    if a != b:  # 最后一个节点不同，说明不相交
        return None
        
    # 根据长度差的正负，确定哪个是长链表，哪个是短链表
    # a指向长链表的头，b指向短链表的头
    if diff >= 0:
        a = h1  # a指向长链表
        b = h2  # b指向短链表
    else:
        a = h2
        b = h1
        
    diff = abs(diff)

    while diff != 0:
        a = a.next
        diff -= 1
        
    # 同时移动直到相遇
    while a != b:
        a = a.next
        b = b.next
        
    return a  # 返回交点

算法分析

  • 时间复杂度：O(M + N)，M和N分别是两个链表的长度
  • 空间复杂度：O(1)
  • 核心技巧：长度差计算 + 双指针

题目二：每k个节点一组翻转链表

问题描述

给定一个链表，每k个节点一组进行翻转，如果最后剩余节点不够k个，则保持原样。

测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/

解题思路

容器解法：把所有节点都放到数组里，然后每k个节点一组进行翻转，但空间复杂度为O(N)。

最优解法：使用有限变量完成分组翻转。

每k个节点一组反转链表

每k个节点一组反转链表-reverse过程

每k个节点一组反转链表-找lastteamend

算法步骤

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
# 按k个一组翻转链表
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
    start = head  # start指向当前组的开始节点
    end = self.teamEnd(start, k)  # 找到第一组的结束节点
    
    if end is None:  # 如果第一组的长度不足k，直接返回原链表头节点
        return head
    
    # 第一组很特殊因为牵扯到换头的问题
    # 翻转后，第一组的末尾节点end会成为整个链表的新头节点
    head = end
    self.reverse(start, end)  # 翻转第一组节点
    
    # 翻转之后start变成了上一组的结尾节点
    lastTeamEnd = start  # lastTeamEnd记录上一组翻转后的尾节点
    
    # 循环处理剩余的链表
    while lastTeamEnd.next is not None:
        start = lastTeamEnd.next  # 下一组的开始节点
        end = self.teamEnd(start, k)  # 找到下一组的结束节点
        
        if end is None:  # 如果剩余部分的长度不足k，直接返回头节点，不进行翻转
            return head
        
        self.reverse(start, end)  # 翻转当前组
        lastTeamEnd.next = end  # 将上一组的尾节点与当前组翻转后的头节点(即原来的end)连接起来
        lastTeamEnd = start  # 更新lastTeamEnd为当前组翻转后的尾节点(即原来的start)
        
    return head  # 返回新的头节点

# 当前组的开始节点是s，往下数k个找到当前组的结束节点返回
def teamEnd(self, s: ListNode, k: int) -> ListNode:
    """找到从s开始第k个节点"""
    # 从s开始，向后移动k-1次
    while k - 1 != 0 and s is not None:
        s = s.next  # s指针后移
        k -= 1  # 计数器减1
    return s  # 返回第k个节点，如果不足k个则返回None

# s -> a -> b -> c -> e -> 下一组的开始节点
# 上面的链表通过如下的reverse方法调整成 : e -> c -> b -> a -> s -> 下一组的开始节点
# 翻转从s到e的这一段链表
def reverse(self, s: ListNode, e: ListNode):
    """翻转从s到e的链表段"""
    e = e.next  # e是当前组的结尾，e.next指向下一组的开头
    pre = None  # pre是前一个节点，初值为None
    cur = s  # cur是当前节点，初值为s
    next_node = None  # next是下一个节点
    
    # 遍历当前组，直到cur到达下一组的开头
    while cur != e:
        next_node = cur.next  # 保存当前节点的下一个节点
        cur.next = pre  # 将当前节点的next指针指向前一个节点
        pre = cur  # pre, cur向后移动
        cur = next_node
    
    s.next = e  # 翻转后，原来的头节点s变成了尾节点，它的next应该指向下一组的开头

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)
  • 核心技巧：分组处理 + 局部翻转

题目三：复制带随机指针的链表

问题描述

复制一个带random指针的链表，random可以指向链表中的任意节点或者null。

测试链接：https://leetcode.cn/problems/copy-list-with-random-pointer/

解题思路

容器解法：使用哈希表记录原节点和新节点的对应关系，空间复杂度O(N)。

最优解法：在原链表上直接操作，分三步完成复制。

拷贝随机指针

算法步骤

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
def copyRandomList(self, head: 'Node') -> 'Node':
    if head is None:  # 如果头节点为空，直接返回None
        return None
    
    cur = head  # cur指针用于遍历原链表
    next_node = None  # next指针用于暂存下一个节点
    
    # 1 -> 2 -> 3 -> ...变成 : 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> ...
    # 第一步：复制每个节点并将其插入到原节点之后
    while cur is not None:
        next_node = cur.next  # 保存原节点的下一个节点
        cur.next = self.Node(cur.val)  # 创建新节点，值为原节点的值
        cur.next.next = next_node  # 将新节点的next指向原节点的下一个节点
        cur = next_node  # 移动cur到下一个原节点
    
    cur = head  # cur指针重置回头节点，准备设置新节点的random指针
    copy = None  # copy指针用于指向复制的节点
    
    # 第二步：为新节点设置random指针
    while cur is not None:
        next_node = cur.next.next  # 保存下一个原节点的位置
        copy = cur.next  # 获取当前节点的复制节点
        # 设置复制节点的random指针
        # 如果原节点的random不为空，则其复制节点的random指向原节点random的下一个节点(即random指向节点的复制品)
        copy.random = cur.random.next if cur.random is not None else None
        cur = next_node  # 移动cur到下一个原节点
        
    ans = head.next  # ans是新链表的头节点，即原头节点的下一个节点
    cur = head  # cur指针重置回头节点，准备分离新旧链表
    
    # 第三步：分离原链表和新链表
    while cur is not None:
        next_node = cur.next.next  # 保存下一个原节点的位置
        copy = cur.next  # 获取当前节点的复制节点
        cur.next = next_node  # 恢复原链表的next指针
        # 设置复制节点的next指针
        # 如果下一个原节点不为空，则复制节点的next指向下一个原节点的复制节点
        copy.next = next_node.next if next_node is not None else None
        cur = next_node  # 移动cur到下一个原节点
        
    return ans  # 返回新链表的头节点

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)
  • 核心技巧：节点插入 + 关系复制 + 链表分离

题目四：判断链表是否是回文结构

问题描述

判断链表是否是回文结构，一个链表节点视为一个字符。

测试链接：https://leetcode.cn/problems/palindrome-linked-list/

解题思路

容器解法：使用栈存储所有节点，然后比较压栈过程和弹栈过程的数字是不是一致的，空间复杂度O(N)。

最优解法：使用快慢指针找中点，翻转后半部分，然后比较。

算法步骤

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
# 提交如下的方法
def isPalindrome(self, head: ListNode) -> bool:
    if head is None or head.next is None:  # 空链表或只有一个节点的链表是回文结构
        return True
    
    slow = head  # slow指针每次走一步，fast指针每次走两步
    fast = head
    
    # 找中点，当fast到达链表末尾时，slow正好在中间位置
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next  # slow指针后移一步
        fast = fast.next.next  # fast指针后移两步
        
    # 现在中点就是slow，从中点开始往后的节点逆序
    pre = slow  # pre是反转后的链表的头节点，初始是slow
    cur = pre.next  # cur是当前要处理的节点，初始是slow的下一个
    next_node = None  # next_node用于保存cur的下一个节点
    pre.next = None  # 断开前半部分和后半部分的连接
    
    # 循环反转后半部分链表
    while cur is not None:
        next_node = cur.next  # 保存下一个节点
        cur.next = pre  # 当前节点的next指向前一个节点(pre)
        pre = cur  # pre和cur指针后移
        cur = next_node
        
    # 上面的过程已经把链表调整成从左右两侧往中间指
    # head -> ... -> slow <- ... <- pre
    ans = True  # ans默认为True，即假设是回文
    left = head  # left指针从头开始
    right = pre  # right指针从后半部分的头（即反转前的尾）开始
    
    # left往右、right往左，每一步比对值是否一样，如果某一步不一样答案就是false
    while left is not None and right is not None:
        if left.val != right.val:  # 如果左右两边的值不相等
            ans = False  # 那么不是回文
            break  # 退出循环
        left = left.next  # 移动指针
        right = right.next
        
    # 本着不坑的原则，把链表调整回原来的样子再返回判断结果
    # 再次反转后半部分，恢复原链表结构
    cur = pre.next  # cur是当前要处理的节点，初始是pre的下一个
    pre.next = None  # 断开连接
    next_node = None  # next_node用于保存cur的下一个节点
    
    # 循环将后半部分链表反转回来
    while cur is not None:
        next_node = cur.next  # 保存下一个节点
        cur.next = pre  # 当前节点的next指向前一个节点(pre)
        pre = cur  # pre和cur指针后移
        cur = next_node
        
    return ans  # 返回最终的判断结果

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)
  • 核心技巧：快慢指针找中点 + 链表翻转

题目五：返回链表的第一个入环节点

问题描述

判断链表是否有环，如果有环，返回入环节点，否则返回None。

测试链接：https://leetcode.cn/problems/linked-list-cycle-ii/

解题思路

容器解法：用哈希表记录每个节点，如果某个节点再次出现，则该节点就是入环节点。

最优解法：使用快慢指针，分两阶段找环。

快慢指针会在入环处相遇

数学原理

设链表头到入环点距离为a，入环点到相遇点距离为b，相遇点到入环点距离为c。

当快慢指针相遇时：

  • 慢指针走过距离：a + b
  • 快指针走过距离：a + b + c + b = a + 2b + c

由于快指针速度是慢指针的2倍：
2(a + b) = a + 2b + c
解得：a = c

算法步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def detectCycle(self, head: ListNode) -> ListNode:
    if head is None or head.next is None or head.next.next is None:
        return None
        
    slow = head.next  # 慢指针slow每次走一步
    fast = head.next.next  # 快指针fast每次走两步
    
    # 第一阶段：快慢指针相遇
    while slow != fast:
        if fast.next is None or fast.next.next is None:  # 如果快指针或其下一个节点为空，说明没有环
            return None
        slow = slow.next  # 慢指针走一步
        fast = fast.next.next  # 快指针走两步
        
    # 第二阶段：快指针回到头部，同步移动
    fast = head  # 当快慢指针相遇后，将快指针重置到链表头
    # 此时，慢指针和快指针同时以每次一步的速度前进
    while slow != fast:
        slow = slow.next  # 慢指针后移
        fast = fast.next  # 快指针后移
        
    return slow  # 相遇点即为入环点

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)
  • 核心技巧：快慢指针 + 数学推导

题目六：链表排序

问题描述

在链表上排序，要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求排序有稳定性。

测试链接：https://leetcode.cn/problems/sort-list/

解题思路

链表由于有指针存在可以做到这个指标，但是数组排序不行。使用自底向上的归并排序，采用非递归方法避免O(logn)的递归空间。

算法步骤

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
def findEnd(self, s: ListNode, k: int) -> ListNode:
    """从s开始找第k个节点"""
    while s and s.next and k - 1 > 0:
        s = s.next
        k -= 1
    return s

# l1...r1 -> null : 有序的左部分 (在Python实现中r1,r2参数是不必要的)
# l2...r2 -> null : 有序的右部分
# 整体merge在一起，保证有序
# 并且返回整体的头和尾
def merge(self, l1: ListNode, l2: ListNode) -> (ListNode, ListNode):
    """合并两个有序链表，返回头和尾"""
    dummy = self.ListNode(0)  # dummy是哨兵节点，方便处理
    pre = dummy  # pre指针用于构建新链表
    
    # 当两个链表都不为空时
    while l1 and l2:
        # 比较两个链表节点的值
        if l1.val <= l2.val:
            pre.next = l1  # 将较小的节点连接到新链表
            l1 = l1.next  # 移动l1指针
        else:
            pre.next = l2  # 将较小的节点连接到新链表
            l2 = l2.next  # 移动l2指针
        pre = pre.next  # 移动pre指针
    
    # 如果l1还有剩余，直接连接
    if l1:
        pre.next = l1
    elif l2:  # 如果l2还有剩余，直接连接
        pre.next = l2
        
    # 找到合并后链表的尾部
    while pre.next:
        pre = pre.next
        
    return dummy.next, pre  # 返回新链表的头和尾

def sortList(self, head: ListNode) -> ListNode:
    """正式排序"""
    if not head:  # 如果链表为空，直接返回
        return None
    
    n = 0  # n用于存储链表长度
    cur = head  # cur用于遍历链表
    # 计算链表长度
    while cur:
        n += 1
        cur = cur.next
        
    # l1...r1 每组的左部分
    # l2...r2 每组的右部分
    # next_group_head 下一组的开头
    # last_team_end 上一组的结尾
    
    step = 1  # step是每次合并的子链表长度，从1开始，每次翻倍
    while step < n:
        # 每一轮归并开始时，重新从头开始，dummy是一个哨兵节点，方便处理头节点
        dummy = self.ListNode(0, head)
        last_team_end = dummy  # last_team_end指向上一次合并后的尾部
        cur = dummy.next  # cur指向当前处理的链表的头部
        
        while cur:       
            l1 = cur  # l1是第一部分的头
            r1 = self.findEnd(l1, step)  # r1是第一部分的尾
            l2 = r1.next if r1 else None  # l2是第二部分的头
            if not l2:  # 如果没有第二部分，就结束这一轮的合并
                last_team_end.next = l1
                break
            r2 = self.findEnd(l2, step)  # r2是第二部分的尾
            
            next_group_head = r2.next if r2 else None  # next_group_head是下一组的头
            
            # 断开链表，准备合并
            r1.next = None
            r2.next = None
            
            merged_head, merged_end = self.merge(l1, l2)  # 合并l1和l2两个有序链表
            
            last_team_end.next = merged_head  # 将合并后的链表接在上一组的后面
            last_team_end = merged_end  # 更新last_team_end为当前合并后的尾部
            
            cur = next_group_head  # cur指向下一组的开头
        
        head = dummy.next  # 更新整个链表的头
        step <<= 1  # 步长翻倍
        
    return head


算法分析

  • 时间复杂度：O(N*logN)
  • 空间复杂度：O(1)
  • 稳定性：是
  • 核心技巧：自底向上归并 + 非递归实现

链表问题核心技巧总结

1. 快慢指针技巧

快慢指针是链表问题中最重要的技巧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 找链表中点
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow指向中点

# 判断链表是否有环
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True  # 有环
return False

2. 虚拟头节点技巧

当需要修改头节点时，使用虚拟头节点简化操作：

1
2
3
4
dummy = ListNode(0)
dummy.next = head
# 对dummy.next进行操作
return dummy.next

3. 双指针技巧

用于处理需要同时操作两个位置的问题：

1
2
3
4
5
6
7
8
9
# 删除倒数第n个节点
dummy = ListNode(0, head)
first = second = dummy
for _ in range(n + 1):
    first = first.next
while first:
    first = first.next
    second = second.next
second.next = second.next.next

4. 链表翻转技巧

翻转是链表的基础操作：

1
2
3
4
5
6
7
8
9
def reverse(head):
    pre = None
    cur = head
    while cur:
        next_node = cur.next
        cur.next = pre
        pre = cur
        cur = next_node
    return pre

复杂度分析总结

题目 时间复杂度 空间复杂度 核心技巧
链表相交 O(M+N) O(1) 长度差+双指针
K组翻转 O(N) O(1) 分组+局部翻转
复制随机链表 O(N) O(1) 节点插入+分离
回文判断 O(N) O(1) 快慢指针+翻转
环检测 O(N) O(1) 快慢指针+数学
链表排序 O(N*logN) O(1) 自底向上归并

学习建议

  1. 重视编程能力：链表题目主要考察coding能力，要多练习用有限变量解决问题

  2. 掌握核心技巧：

    • 快慢指针（最重要）
    • 虚拟头节点
    • 双指针
    • 链表翻转

  3. 避免容器方法：在练习时尽量使用O(1)空间的方法，提升编程能力

  4. 注意边界条件：

    • 空链表
    • 单节点链表
    • 链表长度不足的情况

  5. 保持链表结构：某些题目要求恢复原链表结构，要特别注意

链表问题虽然算法相对简单，但对编程能力要求较高。通过大量练习和对核心技巧的熟练掌握，可以有效提升解题能力。