当前位置:

首页 > 编程开发 > 链表的基础算法(Python)

链表的基础算法(Python)

1. 什么是链表 想象一下,你有一串珍珠项链。每颗珍珠(数据)都通过一根细线(指针)连接到下一颗珍珠。你可以轻松地在中间插入一颗新珍珠,或者取下一颗旧的,只需要调整几根线的连接,而不必像数组那样,把后面所有的珍珠都挪动位置。这就是链表(Linked List)——一种线性数据结构,它的元素在内存中不

本文目录

    1. 什么是链表

    想象一下,你有一串珍珠项链。每颗珍珠(数据)都通过一根细线(指针)连接到下一颗珍珠。你可以轻松地在中间插入一颗新珍珠,或者取下一颗旧的,只需要调整几根线的连接,而不必像数组那样,把后面所有的珍珠都挪动位置。这就是链表(Linked List)——一种线性数据结构,它的元素在内存中不必连续存放,每个元素由一个节点(Node)表示,节点包含数据域和指向下一个节点的指针(引用)。

    相比数组,链表的插入与删除效率更高,但代价是随机访问较慢,因为你必须从第一颗珍珠开始,一颗一颗数过去。

    常见的链表类型主要有三种:

    • 单链表(Singly Linked List):只能单向前进。
    • 双向链表(Doubly Linked List):可以向前也可以向后。
    • 循环链表(Circular Linked List):首尾相连,形成一个环。

    2. 单链表

    2.1 节点定义

    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next
    

    这个结构非常直观:val 就是珍珠本身(存储的数据),next 就是那根指向下一颗珍珠的线。如果 next 是 None,那就意味着这是项链的最后一颗珍珠。

    2.2 基本操作

    掌握了节点的结构,接下来看看如何操作这根“珍珠项链”。

    遍历链表:从头开始,沿着 next 指针一路走下去。

    def tra verse(head):
        cur = head
        while cur:
            print(cur.val, end=' -> ')
            cur = cur.next
        print('None')
    

    在头部插入节点:这就像制作一条新项链,先把新珍珠的线连到旧的第一颗珍珠上,然后宣布这颗新珍珠成为项链的新起点。

    def insert_at_head(head, val):
        new_node = ListNode(val)
        new_node.next = head
        return new_node
    

    在尾部插入节点:需要先走到项链的末端,再把最后一颗珍珠的线系到新珍珠上。

    def insert_at_tail(head, val):
        new_node = ListNode(val)
        if not head:
            return new_node
        cur = head
        while cur.next:
            cur = cur.next
        cur.next = new_node
        return head
    

    删除节点:找到目标珍珠的前一颗珍珠,然后把它的线直接绕过目标,连接到再下一颗珍珠上。目标珍珠虽然还在,但已经没有任何线连接它,相当于从项链上取下来了。

    def delete_node(head, target):
        if not head:
            return None
        if head.val == target:
            return head.next
        cur = head
        while cur.next:
            if cur.next.val == target:
                cur.next = cur.next.next
                return head
            cur = cur.next
        return head
    

    反转链表:这是一个经典操作。思路是,把每一颗珍珠的指向都反过来。你需要三个指针:一个指向前一颗珍珠(prev),一个指向当前珍珠(cur),还有一个临时保存下一颗珍珠(next_node),防止断线。

    def reverse_list(head):
        prev = None
        cur = head
        while cur:
            next_node = cur.next
            cur.next = prev
            prev = cur
            cur = next_node
        return prev
    

    3. 双向链表

    单链表只能向前走,万一错过了想回头怎么办?双向链表给每张“纸条”加上了“上一张纸条的位置”。这样你就可以自由前进或后退了。

    每个节点有两个指针:prev 和 next。

    class DoubleListNode:
        def __init__(self, val=0, prev=None, next=None):
            self.val = val
            self.prev = prev
            self.next = next
    

    在头部插入节点:操作稍多一步,需要维护好新节点和原头节点之间的双向链接。

    def dll_insert_head(head, val):
        new_node = DoubleListNode(val)
        new_node.next = head
        if head:
            head.prev = new_node
        return new_node
    

    删除节点:在已知节点引用的情况下,删除变得异常简单,只需要调整其前驱和后继节点的指针即可。

    def dll_delete_node(node):
        if node.prev:
            node.prev.next = node.next
        if node.next:
            node.next.prev = node.prev
    

    4. 循环链表

    单循环链表:让尾节点的 next 指向头节点,形成一个环。约瑟夫问题就是它的经典应用场景。

    def create_circular_list(values):
        if not values:
            return None
        head = ListNode(values[0])
        cur = head
        for v in values[1:]:
            cur.next = ListNode(v)
            cur = cur.next
        cur.next = head
        return head
    

    遍历循环链表时需要特别注意终止条件,常用的方法是从头开始,当再次遇到头节点时停止。

    5. 典型例题

    5.1 反转列表

    迭代法已经在 2.2 节给出。递归法则提供了一种更优雅的思路:

    def reverse_list_recursive(head):
        if not head or not head.next:
            return head
        new_head = reverse_list_recursive(head.next)
        head.next.next = head
        head.next = None
        return new_head
    

    递归过程就像是把一列火车从后向前一节节卸下来重新组装。尽管代码简洁,但要小心递归深度过大可能导致栈溢出。

    5.2 合并两个有序链表

    这就像有两队按身高排好队的小朋友,我们要把他们合并成一支新队伍。策略很简单:每次比较两队队首的身高,选较矮的加入新队伍,然后该队指针后移。

    def merge_two_lists(l1, l2):
        dummy = ListNode(0)
        cur = dummy
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummy.next
    

    5.3 环形链表检测

    判断链表中是否有环,经典的解决方案是 Floyd 判圈算法,又称“龟兔赛跑”算法。

    我们派两个指针,一个每次走一步(乌龟),一个每次走两步(兔子)。如果赛道有环,兔子最终会追上乌龟;如果没有环,兔子会率先到达终点(None)。

    alt转存失败,建议直接上传图片文件

    def has_cycle(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False
    

    如果要求返回环的入口节点,算法需要稍作调整:

    def detect_cycle(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None
    

    为什么这样能找到入口?简单来说,设头节点到环入口距离为 a,入口到相遇点距离为 b,环长为 L。第一次相遇时,快指针路程是慢指针的两倍,可以推导出 a 一定是 L 的整数倍减去 b。所以让一个指针从开头走 a 步,另一个从相遇点走 a 步(在环里相当于走了 L - b + b 等),它们必定在入口重合。

    5.4 删除链表的倒数第 N 个节点

    利用双指针技巧,让两个指针相距 N 步。当前面的指针走到链表末尾时,后面的指针正好指向待删除节点的前驱。

    def remove_nth_from_end(head, 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
        return dummy.next
    

    5.5 回文链表

    判断链表是否为回文。一个巧妙的思路是:先找到链表中点,反转后半部分,然后同时从头部和反转后的后半部头部开始比较。

    def is_palindrome(head):
        if not head or not head.next:
            return True
        # 找中点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 反转后半
        prev = None
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node
        # 比较
        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True
    

    5.6 两两交换链表中的节点

    给定 1->2->3->4,返回 2->1->4->3。关键在于维护好一个“前驱”指针(prev),每次交换一对节点后,更新这个前驱指针。

    def swap_pairs(head):
        dummy = ListNode(0, head)
        prev = dummy
        while prev.next and prev.next.next:
            first = prev.next
            second = first.next
            first.next = second.next
            second.next = first
            prev.next = second
            prev = first
        return dummy.next
    

    5.7 链表相交

    找到两个单链表相交的起始节点。一个巧妙的解法是:让两个指针分别从两个链表头出发,当走到末尾时,切换到另一个链表的头部继续走。如果两链表相交,它们最终会在交点相遇;如果不相交,最终会同时到达 None。

    def get_intersection_node(headA, headB):
        pa, pb = headA, headB
        while pa != pb:
            pa = pa.next if pa else headB
            pb = pb.next if pb else headA
        return pa
    

    6. 链表常用技巧总结

    • 哑节点(Dummy Node):在链表头部前面添加一个不存储实际值的节点,可以极大地简化边界条件处理,尤其是在头节点可能发生变化的时候。
    • 双指针:快慢指针用于找中点、判断环;前后指针用于删除倒数第 N 个节点。
    • 递归:非常适合处理反转、合并等具有自相似性的问题,但需要注意递归深度可能导致的栈溢出。
    • 就地操作:对于反转、重排等操作,尽量使用 O(1) 的额外空间,直接在原链表上修改指针。

    7. 复杂度分析

    操作 数组 链表
    随机访问 O(1) O(n)
    头部插入 O(n) O(1)
    尾部插入 O(1) 均摊 O(n) 无尾指针, O(1) 有尾指针
    删除节点 O(n) O(1) 若已知前驱
    查找 O(n) O(n)

    从表格可以清晰地看出,链表在需要频繁插入、删除且不需要随机访问的场景下表现优异,而数组则在需要快速按索引访问时更胜一筹。选择哪种数据结构,取决于你的具体需求。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发 Python
    相关文章 更多
    python删除一个列表里的重复元素的方法与代码示例
    python删除一个列表里的重复元素的方法与代码示例

    学习如何使用Python高效删除列表中的重复元素。本文提供5种常见方法的代码示例,涵盖保持顺序与不保持顺序的场景,适合初学者和进阶开发者参考。

    Python写接口的步骤及完整代码示例
    Python写接口的步骤及完整代码示例

    详细讲解使用Python编写Web接口的核心步骤与完整代码示例,涵盖环境准备、路由定义、数据校验、服务启动及调试测试方法。

    codex怎么读取word文档及docx文件操作教程
    codex怎么读取word文档及docx文件操作教程

    介绍如何利用编程工具读取和解析Word文档(docx格式),涵盖基础文本提取代码示例、结构化数据处理逻辑,以及处理复杂排版时的技术局限与替代方案。

    怎么在Python中调用C语言代码提升性能
    怎么在Python中调用C语言代码提升性能

    详细讲解在Python中调用C语言代码提升性能的完整实践指南,包含原理分析、编译步骤、ctypes与CFFI具体实现、性能对比及常见陷阱。

    Python与C语言的性能差异及底层原理
    Python与C语言的性能差异及底层原理

    深入解析Python与C语言在执行效率上的数量级差异,从编译机制、变量内存布局、动态类型推断到GIL锁,系统阐明底层核心原理。

    Python和C语言哪个更适合编程入门
    Python和C语言哪个更适合编程入门

    客观对比Python与C语言在心智负担、底层机制与学习反馈上的核心差异,提供清晰有据的选择标准与切实的入门学习路径。

    selenium上传文件教程本地文件路径设置方法
    selenium上传文件教程本地文件路径设置方法

    深入解析Selenium处理文件上传的技术细节,涵盖标准HTML控件的路径直接注入法与非标准控件的系统级模拟方案,提供Windows与Linux环境下的路径设置最佳实践及常见异常排查。

    大数据开发语言选型:Java对比Scala与Python的优缺点及适用场景
    大数据开发语言选型:Java对比Scala与Python的优缺点及适用场景

    针对大数据工程场景,系统对比Java、Scala与Python在执行性能、生态结合、开发效率和维护成本上的核心差异,给出清晰的架构选型依据与落地方案。

    langgraph python guide中文入门教程详解
    langgraph python guide中文入门教程详解

    本篇LangGraph Python中文入门教程详解,系统梳理StateGraph状态机定义、节点编写、边与条件路由、检查点持久化(MemorySaver)等核心机制,提供从环境安装到完整循环智能体构建的代码示例与实操指导。

    Windows 安装 Python:从官方入口到虚拟环境的可复现实践
    Windows 安装 Python:从官方入口到虚拟环境的可复现实践

    面向后端开发者,基于 Python 官方文档说明如何在 Windows 上安装 Python、创建 venv 虚拟环境及使用 pip 管理依赖。包含可复制命令、验证方法及工具选择边界,避免常见配置误区。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。