Blog of AgioPan
0%

数据结构与算法自学笔记（2）- 链表相关

Posted on Edited on In ,

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series
本笔记包括了class009 -> class012，涵盖了链表的基础概念、反转操作、合并算法、链表运算以及分割技巧等内容。

009【入门】单双链表及其反转

链表的基本概念

链表是一种线性数据结构，其中元素存储在节点中，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的元素在内存中不必连续存储。

单链表节点定义

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

双链表节点定义

1
2
3
4
5
6
7
8
9
class DoubleListNode:
    """
    双链表节点类
    每个节点有两个指针：指向前驱和后继
    """
    def __init__(self, value):
        self.value = value                # 节点存储的数据值
        self.last = None                  # 指向前一个节点的指针
        self.next = None                  # 指向下一个节点的指针

单链表反转算法

反转单链表测试链接 : https://leetcode.cn/problems/reverse-linked-list/

迭代方法实现

单链表反转是链表操作中的经典问题，核心思想是改变节点间的指针方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class ListReverseOperations:
    @staticmethod
    def reverse_linked_list(head):
        """
        反转单链表 - 迭代实现
        时间复杂度: O(n), 空间复杂度: O(1)
        
        参数: head - 链表头节点
        返回: 反转后链表的头节点
        """
        pre = None                        # 前驱节点指针，初始为None
        next_node = None                  # 临时保存下一个节点
        
        while head is not None:           # 遍历整个链表
            next_node = head.next         # 保存下一个节点，防止链表断裂
            head.next = pre               # 当前节点指向前驱（反转指针）
            pre = head                    # 前驱指针前进到当前节点
            head = next_node              # 头指针前进到下一个节点
        
        return pre                        # pre此时指向原链表的尾节点，即新链表的头节点

反转过程图解

反转图解

具体在上面的实现中，是利用next向后移动 利用pre改变方指针向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
原链表: 1 -> 2 -> 3 -> 4 -> 5 -> NULL

第1步: pre=NULL, head=1, next=2
      NULL <- 1    2 -> 3 -> 4 -> 5 -> NULL
             pre  head

第2步: pre=1, head=2, next=3  
      NULL <- 1 <- 2    3 -> 4 -> 5 -> NULL
                  pre  head

第3步: pre=2, head=3, next=4
      NULL <- 1 <- 2 <- 3    4 -> 5 -> NULL
                        pre  head

最终: NULL <- 1 <- 2 <- 3 <- 4 <- 5
                                  pre

递归方法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@staticmethod
def reverse_linked_list_recursive(head):
    """
    反转单链表 - 递归实现
    时间复杂度: O(n), 空间复杂度: O(n) - 递归栈空间
    
    参数: head - 链表头节点
    返回: 反转后链表的头节点
    """
    # 基础情况：空链表或单节点链表
    if head is None or head.next is None:
        return head
    
    # 递归反转剩余部分
    new_head = ListReverseOperations.reverse_linked_list_recursive(head.next)
    
    # 反转当前节点与下一个节点的连接
    head.next.next = head             # 下一个节点指回当前节点
    head.next = None                  # 当前节点的next置空
    
    return new_head                   # 返回新的头节点

双链表反转算法

双链表的反转需要同时处理前驱和后继两个指针，相比单链表更加复杂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@staticmethod
def reverse_double_list(head):
    """
    反转双链表
    时间复杂度: O(n), 空间复杂度: O(1)
    
    参数: head - 双链表头节点
    返回: 反转后双链表的头节点
    """
    pre = None                        # 前驱节点指针
    next_node = None                  # 临时保存下一个节点
    
    while head is not None:           # 遍历整个双链表
        next_node = head.next         # 保存下一个节点
        
        # 交换当前节点的前驱和后继指针
        head.next = pre               # next指向前驱
        head.last = next_node         # last指向后继
        
        pre = head                    # 前驱指针前进
        head = next_node              # 头指针前进
    
    return pre                        # 返回新的头节点

双链表反转的关键点

  1. 指针交换：每个节点的next和last指针需要互换方向
  2. 边界处理：正确处理链表两端的NULL指针
  3. 遍历顺序：确保在修改指针前保存必要的信息

010【入门】合并两个有序链表

测试链接 : https://leetcode.cn/problems/merge-two-sorted-lists/

问题描述

给定两个已排序的链表，将它们合并成一个新的有序链表。新链表应该通过拼接给定的两个链表的所有节点组成。

算法思想

采用双指针技术，比较两个链表当前节点的值，选择较小的节点添加到结果链表中，然后移动对应的指针。

实现方案

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
class Solution:
    @staticmethod
    def merge_two_lists(head1, head2):
        """
        合并两个有序链表
        时间复杂度: O(m + n), 空间复杂度: O(1)
        
        参数: head1, head2 - 两个有序链表的头节点
        返回: 合并后有序链表的头节点
        """
        # 边界情况处理：其中一个链表为空
        if head1 is None or head2 is None:
            return head2 if head1 is None else head1
        
        # 确定合并后链表的头节点
        if head1.val <= head2.val:
            head = head1                  # head1的值更小，作为头节点
            cur1 = head1.next             # cur1指向head1的下一个节点
            cur2 = head2                  # cur2指向head2的当前节点
        else:
            head = head2                  # head2的值更小，作为头节点
            cur1 = head1                  # cur1指向head1的当前节点
            cur2 = head2.next             # cur2指向head2的下一个节点
        
        pre = head                        # pre用于构建结果链表
        
        # 双指针遍历两个链表
        while cur1 is not None and cur2 is not None:
            if cur1.val <= cur2.val:     # cur1的值更小或相等
                pre.next = cur1           # 将cur1连接到结果链表
                cur1 = cur1.next          # cur1指针后移
            else:                         # cur2的值更小
                pre.next = cur2           # 将cur2连接到结果链表
                cur2 = cur2.next          # cur2指针后移
            pre = pre.next                # 结果链表指针后移
        
        # 处理剩余节点：将未遍历完的链表直接连接到结果链表末尾
        pre.next = cur1 if cur1 is not None else cur2
        
        return head                       # 返回合并后链表的头节点

算法优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@staticmethod
def merge_two_lists_optimized(head1, head2):
    """
    合并两个有序链表 - 优化版本
    使用虚拟头节点简化边界处理
    """
    dummy = ListNode(0)               # 创建虚拟头节点
    current = dummy                   # 当前指针指向虚拟头节点
    
    # 双指针遍历两个链表
    while head1 is not None and head2 is not None:
        if head1.val <= head2.val:
            current.next = head1      # 连接较小节点
            head1 = head1.next        # 移动head1指针
        else:
            current.next = head2      # 连接较小节点
            head2 = head2.next        # 移动head2指针
        current = current.next        # 移动结果链表指针
    
    # 连接剩余节点
    current.next = head1 if head1 is not None else head2
    
    return dummy.next                 # 返回真正的头节点

合并过程示例

1
2
3
4
5
6
7
8
9
10
链表1: 1 -> 2 -> 4
链表2: 1 -> 3 -> 4

合并过程:
step1: 比较1和1，选择链表1的1    结果: 1
step2: 比较2和1，选择链表2的1    结果: 1 -> 1  
step3: 比较2和3，选择链表1的2    结果: 1 -> 1 -> 2
step4: 比较4和3，选择链表2的3    结果: 1 -> 1 -> 2 -> 3
step5: 比较4和4，选择链表1的4    结果: 1 -> 1 -> 2 -> 3 -> 4
step6: 连接剩余的4              结果: 1 -> 1 -> 2 -> 3 -> 4 -> 4

011【入门】两个链表相加

测试链接：https://leetcode.cn/problems/add-two-numbers/

问题描述

给定两个非空链表来表示两个非负整数，数字最高位位于链表开始位置。它们的每个节点只存储一位数字，计算两个数的和并以相同形式返回一个表示和的链表。

核心思想

模拟手工加法运算，从链表尾部开始逐位相加，处理进位问题。

算法实现

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
class Solution:
    @staticmethod
    def add_two_numbers(h1, h2):
        """
        两个链表数字相加
        时间复杂度: O(max(m,n)), 空间复杂度: O(max(m,n))
        
        参数: h1, h2 - 两个表示数字的链表头节点
        返回: 表示和的链表头节点
        """
        ans = None                        # 结果链表头节点
        cur = None                        # 当前构建位置指针
        carry = 0                         # 进位标志
        
        # 遍历两个链表，直到都为空
        while h1 is not None or h2 is not None:
            # 获取当前位的数字，如果链表已结束则为0
            val1 = h1.val if h1 is not None else 0
            val2 = h2.val if h2 is not None else 0
            
            # 计算当前位的和（包括进位）
            total = val1 + val2 + carry
            carry = total // 10           # 计算新的进位
            digit = total % 10            # 当前位的数字
            
            # 构建结果链表
            if ans is None:               # 第一个节点
                ans = ListNode(digit)
                cur = ans
            else:                         # 后续节点
                cur.next = ListNode(digit)
                cur = cur.next
            
            # 移动链表指针
            h1 = h1.next if h1 is not None else None
            h2 = h2.next if h2 is not None else None
        
        # 处理最后的进位
        if carry == 1:
            cur.next = ListNode(1)
        
        return ans                        # 返回结果链表头节点

代码修正与优化

优化了源代码最后的进位问题

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
@staticmethod
def add_two_numbers_corrected(h1, h2):
    """
    两个链表数字相加 - 优化版本，更加通用
    """
    ans = None                        # 结果链表头节点
    cur = None                        # 当前构建位置指针
    carry = 0                         # 进位标志
    
    while h1 is not None or h2 is not None:
        # 安全获取节点值，避免空指针异常
        val1 = h1.val if h1 is not None else 0
        val2 = h2.val if h2 is not None else 0
        
        # 计算当前位的和
        total = val1 + val2 + carry
        carry = total // 10           # 新进位
        digit = total % 10            # 当前位数字
        
        # 构建结果链表节点
        new_node = ListNode(digit)
        if ans is None:               # 初始化头节点
            ans = cur = new_node
        else:                         # 连接新节点
            cur.next = new_node
            cur = new_node
        
        # 安全移动指针
        h1 = h1.next if h1 is not None else None
        h2 = h2.next if h2 is not None else None
    
    # 处理最终进位
    if carry > 0:
        cur.next = ListNode(carry)
    
    return ans

算法示例

1
2
3
4
5
6
7
8
9
10
链表1: 2 -> 4 -> 3  (表示数字342)
链表2: 5 -> 6 -> 4  (表示数字465)

相加过程:
位置0: 2 + 5 + 0(进位) = 7, 进位=0  结果: 7
位置1: 4 + 6 + 0(进位) = 10, 进位=1  结果: 7 -> 0
位置2: 3 + 4 + 1(进位) = 8, 进位=0  结果: 7 -> 0 -> 8

最终结果: 7 -> 0 -> 8 (表示数字807)
验证: 342 + 465 = 807 ✓

边界情况处理

  1. 不同长度链表：短链表结束后，继续处理长链表的剩余位
  2. 最高位进位：最后可能产生新的最高位
  3. 空链表：输入验证，确保链表非空
  4. 单位数：正确处理个位数相加的情况

012【入门】划分链表

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

问题描述

给定一个链表和一个特定值x，对链表进行分隔，使得所有小于x的节点都在大于或等于x的节点之前。保持两个分区中每个节点的初始相对位置。

算法思想

使用双链表分离的思想：

  1. 创建两个独立的链表：小于x的节点链表和大于等于x的节点链表
  2. 遍历原链表，将节点分别添加到对应的链表中
  3. 最后将两个链表连接起来

实现方案

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
class Solution:
    @staticmethod
    def partition(head, x):
        """
        划分链表
        时间复杂度: O(n), 空间复杂度: O(1)
        
        参数: head - 链表头节点, x - 划分值
        返回: 划分后链表的头节点
        """
        # 初始化两个链表的头尾指针
        left_head = None                  # 小于x的链表头指针
        left_tail = None                  # 小于x的链表尾指针
        right_head = None                 # 大于等于x的链表头指针
        right_tail = None                 # 大于等于x的链表尾指针
        
        next_node = None                  # 临时保存下一个节点
        
        # 遍历原链表，分离节点
        while head is not None:
            next_node = head.next         # 保存下一个节点
            head.next = None              # 断开当前节点的连接
            
            if head.val < x:              # 当前节点值小于x
                if left_head is None:    # 左链表为空
                    left_head = head      # 设置左链表头节点
                else:                     # 左链表非空
                    left_tail.next = head # 连接到左链表尾部
                left_tail = head          # 更新左链表尾指针
            else:                         # 当前节点值大于等于x
                if right_head is None:   # 右链表为空
                    right_head = head     # 设置右链表头节点
                else:                     # 右链表非空
                    right_tail.next = head # 连接到右链表尾部
                right_tail = head         # 更新右链表尾指针
            
            head = next_node              # 移动到下一个节点
        
        # 连接两个链表
        if left_head is None:            # 如果左链表为空
            return right_head             # 直接返回右链表
        else:                            # 左链表非空
            left_tail.next = right_head   # 连接左右链表
            return left_head              # 返回左链表头节点

代码修正与完善

优化了原代码在遍历阶段的指针指代可能不清晰的问题，修改了if else后的指定

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
class Solution:
    @staticmethod
    def partition_corrected(head, x):
        """
        划分链表 - 修正版本
        修复了原代码的语法错误和逻辑问题
        """
        # 初始化四个指针
        left_head = left_tail = None      # 小于x的链表头尾指针
        right_head = right_tail = None    # 大于等于x的链表头尾指针
        
        # 遍历原链表
        while head is not None:
            next_node = head.next         # 保存下一个节点
            head.next = None              # 断开当前节点
            
            if head.val < x:              # 节点值小于x
                if left_head is None:    # 第一个小于x的节点
                    left_head = left_tail = head
                else:                     # 后续小于x的节点
                    left_tail.next = head
                    left_tail = head
            else:                         # 节点值大于等于x
                if right_head is None:   # 第一个大于等于x的节点
                    right_head = right_tail = head
                else:                     # 后续大于等于x的节点
                    right_tail.next = head
                    right_tail = head
            
            head = next_node              # 移动到下一个节点
        
        # 合并两个链表
        if left_head is None:            # 只有大于等于x的节点
            return right_head
        
        left_tail.next = right_head       # 连接两个链表
        return left_head                  # 返回结果链表头节点

优化版本：使用虚拟头节点

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
@staticmethod
def partition_optimized(head, x):
    """
    划分链表 - 优化版本
    使用虚拟头节点简化代码逻辑，简化了边界处理
    """
    # 创建虚拟头节点
    left_dummy = ListNode(0)          # 小于x链表的虚拟头节点
    right_dummy = ListNode(0)         # 大于等于x链表的虚拟头节点
    
    left = left_dummy                 # 小于x链表的当前指针
    right = right_dummy               # 大于等于x链表的当前指针
    
    # 遍历原链表，分配节点
    while head is not None:
        if head.val < x:
            left.next = head          # 连接到左链表
            left = left.next          # 移动左指针
        else:
            right.next = head         # 连接到右链表
            right = right.next        # 移动右指针
        head = head.next              # 移动原链表指针
    
    # 断开右链表的尾部连接，防止环
    right.next = None
    
    # 连接两个链表
    left.next = right_dummy.next
    
    return left_dummy.next            # 返回真正的头节点

算法示例

1
2
3
4
5
6
7
8
9
10
11
12
原链表: 1 -> 4 -> 3 -> 2 -> 5 -> 2
划分值: x = 3

分离过程:
节点1 < 3: 左链表 = 1
节点4 >= 3: 右链表 = 4  
节点3 >= 3: 右链表 = 4 -> 3
节点2 < 3: 左链表 = 1 -> 2
节点5 >= 3: 右链表 = 4 -> 3 -> 5
节点2 < 3: 左链表 = 1 -> 2 -> 2

最终结果: 1 -> 2 -> 2 -> 4 -> 3 -> 5

算法特点

  1. 稳定性：保持原有的相对顺序
  2. 原地操作：只调整指针，不创建新节点
  3. 时间效率：单次遍历，O(n)时间复杂度
  4. 空间效率：只使用常数额外空间

应用场景

  1. 链表排序的预处理：快速排序的分区操作
  2. 数据分类：按条件将数据分为两组
  3. 链表重组：根据特定规则重新排列链表节点

链表操作技巧拓展

核心技巧与模式

1. 双指针技术

1
2
3
4
5
6
7
8
9
10
def two_pointer_pattern(head):
    """
    双指针模式：快慢指针、左右指针等
    常用于链表中点查找、环检测、倒数第k个节点等
    """
    slow = fast = head                    # 快慢指针初始化
    while fast and fast.next:
        slow = slow.next                  # 慢指针每次移动1步
        fast = fast.next.next             # 快指针每次移动2步
    return slow                           # 返回中点或其他目标位置

2. 虚拟头节点

1
2
3
4
5
6
7
8
9
10
11
12
def dummy_head_pattern(head):
    """
    虚拟头节点模式：简化头节点的特殊处理
    特别适用于可能删除头节点或构建新链表的场景
    """
    dummy = ListNode(0)                   # 创建虚拟头节点
    dummy.next = head                     # 连接原链表
    
    # 在这里进行各种操作
    # ...
    
    return dummy.next                     # 返回真正的头节点

3. 递归模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def recursive_pattern(head):
    """
    递归模式：将复杂问题分解为子问题
    适用于链表反转、删除节点、合并等操作
    """
    # 基础情况
    if head is None or head.next is None:
        return head
    
    # 递归处理子问题
    result = recursive_pattern(head.next)
    
    # 处理当前层
    # ...
    
    return result

4. 节点分离与重组

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
def separate_and_merge_pattern(head):
    """
    分离重组模式：将链表按条件分离后重新组合
    适用于链表划分、奇偶分离、按值分组等
    """
    # 创建多个子链表的头尾指针
    list1_head = list1_tail = None
    list2_head = list2_tail = None
    
    while head:
        next_node = head.next
        head.next = None                  # 断开连接
        
        if condition(head):               # 根据条件分配
            # 添加到list1
            if list1_head is None:
                list1_head = list1_tail = head
            else:
                list1_tail.next = head
                list1_tail = head
        else:
            # 添加到list2
            if list2_head is None:
                list2_head = list2_tail = head
            else:
                list2_tail.next = head
                list2_tail = head
        
        head = next_node
    
    # 重新组合链表
    if list1_tail:
        list1_tail.next = list2_head
    return list1_head if list1_head else list2_head

常见错误与注意事项

1. 空指针处理

1
2
3
4
5
6
7
8
9
# 错误示例
def wrong_example(head):
    return head.next.val                  # 可能导致空指针异常

# 正确示例  
def correct_example(head):
    if head and head.next:                # 先检查再访问
        return head.next.val
    return None

2. 内存泄漏防止

1
2
3
4
5
6
7
8
def prevent_memory_leak(head):
    """
    防止内存泄漏：及时断开不需要的连接
    """
    while head:
        next_node = head.next
        head.next = None                  # 断开连接，防止环
        head = next_node

3. 边界情况处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def handle_edge_cases(head):
    """
    处理边界情况：空链表、单节点链表等
    """
    # 空链表
    if head is None:
        return None
    
    # 单节点链表
    if head.next is None:
        return head
    
    # 正常处理逻辑
    # ...

性能分析与优化

时间复杂度分析

  • 单次遍历操作：O(n) - 反转、合并、查找等
  • 嵌套遍历操作：O(n²) - 某些复杂的链表操作
  • 递归操作：O(n) - 但需要考虑递归栈空间

空间复杂度优化

  • 原地操作：优先使用指针操作而非创建新节点
  • 迭代替代递归：在可能的情况下避免递归栈开销
  • 临时变量最小化：只保存必要的指针变量

实际性能考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def performance_optimized_merge(h1, h2):
    """
    性能优化的链表合并
    减少条件判断和指针操作
    """
    dummy = ListNode(0)
    tail = dummy
    
    while h1 and h2:
        if h1.val <= h2.val:
            tail.next, h1 = h1, h1.next
        else:
            tail.next, h2 = h2, h2.next
        tail = tail.next
    
    # 直接连接剩余部分，无需循环
    tail.next = h1 or h2
    return dummy.next