算法实战笔记：链表的底层逻辑与指针的高阶玩法（二）

算法实战笔记链表的底层逻辑与指针的高阶玩法二如果说数组考察的是对连续内存和边界的极限掌控那么链表Linked List考察的就是对指针调度的空间想象力。很多同学在做链表题时脑子里的思路很清晰但一写代码就立刻遭遇NullPointerException空指针异常或者不小心把链表“弄断了”导致死循环。其实搞定链表只需要掌握两个核心法宝虚拟头节点Dummy Node和双指针法快慢指针。本篇笔记将带你系统拆解链表的五大高频场景助你彻底告别链表恐惧症。一、 降维打击虚拟头节点Dummy Node链表操作中最大的痛点是什么是头节点的尴尬地位。在链表中我们如果想要增删一个节点必须找到它的前驱节点。但是头节点没有前驱节点这就导致我们在编写代码时每次遇到涉及头节点的操作都必须写单独的if逻辑来特殊处理。这种代码不仅冗长而且极易出错。破局之道引入虚拟头节点Dummy Node。我们在真正的头节点前面人为地“造”一个假节点让它的next指向真正的头节点。好处这样一来原来的头节点就变成了普通节点链表中的所有节点都拥有了前驱节点。增删改查的逻辑得到了完美的统一再也不用为头节点写恶心的特殊判断了。二、 扎马步链表的五大基本操作在开始刷高阶算法题之前必须要过基础关。你能否不用任何现成的数据结构纯手写实现一个链表类的以下五个核心操作获取第 index 个节点的数值在链表最前面插入一个节点利用 Dummy Node 轻松搞定在链表最后面插入一个节点在第 index 个节点前插入一个节点删除第 index 个节点避坑指南把这五个操作连贯地写一遍重点体会操作顺序。比如插入节点时一定要先连后断新节点先指向后面的节点前驱节点再指向新节点顺序一反链表就会在内存中彻底丢失。三、 面试试金石反转链表“听说过两天反转链表又写不出来了” 这是一道极其经典、极高频的面经题。反转链表不需要额外申请新的内存空间只需要改变节点间next指针的指向即可。这道题通常有两种解法迭代法双指针/头插法定义一个pre指针初始为 null和一个cur指针指向头节点。遍历链表每次让cur.next指向pre然后pre和cur依次向后平移。递归法逻辑较为绕脑。建议先彻底学透、写熟迭代法再去理解递归法。如果迭代的指针反转过程在脑海里还不清晰强行看递归只会一头雾水。四、 封神技巧双指针在链表中的妙用如果说虚拟头节点解决了边界问题那么双指针法快慢指针就是解决链表复杂问题的银弹。以下三大经典场景全部依赖双指针完美破局场景 1删除链表倒数第 N 个节点只遍历一次链表怎么找到倒数第 N 个节点解法准备一个快指针Fast和一个慢指针Slow都指向虚拟头节点。先让 Fast 走 N 步然后 Fast 和 Slow 同时齐步走。当 Fast 走到链表末尾null时Slow 刚好停在待删除节点的前驱节点上。场景 2找两个单链表的相交节点两个链表长度不同如何找到它们的物理内存交点解法分别遍历求出两链表的长度算出长度差diff。让较长链表的指针先走diff步使得两个链表的剩余长度对齐。接着两个指针同时向后走它们第一次指向同一个节点内存地址相同时即为交点。场景 3环形链表最难理解的智力题如何判断链表有环如果有环如何找到环的入口这道题需要一些数学思维分两步走判断是否有环快指针每次走两步慢指针每次走一步。如果链表有环它们一定会在环内相遇。寻找环入口核心小结论当快慢指针相遇时立刻派出一个新指针 1 从链表头节点出发同时让新指针 2 从相遇点出发两个指针每次都只走一步。当这两个指针相遇时相遇的节点绝对就是环的入口处结语从基础的增删改查到虚拟头节点的防御性编程再到双指针法的空间艺术链表的题目看似千变万化但万变不离其宗。只要你在做题时能在脑海里清晰地画出指针箭头断开与重连的画面并熟练运用 Dummy Node 和双指针链表将成为你算法面试中最稳的得分项。