你好我是林森lsjs我的Github 地址sqyCoder (Qiyang) · GitHub以博文记录成长用心打磨代码与思维目录1. 删除链表中等于给定值 val 的所有节点2. 反转一个单链表3. 链表的中间结点4. 链表中倒数第 k 个结点5. 合并两个有序链表6. 链表分割7. 链表的回文结构8. 两个链表的第一个公共结点总结统一链表节点定义class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }1. 删除链表中等于给定值 val 的所有节点203. 移除链表元素 - 力扣LeetCode首先我们看到这道题要求删除链表中所有值等于 val 的节点。大家先仔细想一想这里会遇到什么问题如果要删除的节点刚好是链表第一个头节点我们直接移动 head 就比较麻烦需要单独写判断。那我们能不能想个办法把头节点和普通节点统一处理哎这里我们就可以引入虚拟头结点 dummy。我们让 dummy 指向原来的 head之后我们拿一个 cur 指针从 dummy 开始遍历。我们不能直接判断 cur 本身因为一旦删掉 cur我们就找不到前面的节点了所以我们判断 cur.next。如果下一个节点的值等于 val直接跳过这个节点如果不相等cur 就往后走。循环走完之后dummy.next 就是处理完成后的链表这样我们就不需要区分头节点特殊情况问题顺利解决。public ListNode removeElements(ListNode head, int val) { ListNode dummy new ListNode(-1); dummy.next head; ListNode cur dummy; while (cur.next ! null) { if (cur.next.val val) { cur.next cur.next.next; } else { cur cur.next; } } return dummy.next; }2. 反转一个单链表206. 反转链表 - 力扣LeetCode首先我们看到题目需要把整条链表反转。第一反应直接修改节点 next但是马上会发现一个问题一旦我们把 cur.next 改成前面节点后面的链表直接丢失链表直接断掉。所以我们必须提前保存后面的节点。我们设置两个指针 pre 初始为 nullcur 指向当前节点。每一轮循环先用 next 记录 cur 后面的节点接着让 cur 指向 pre 完成反转之后 pre 移动到 curcur 移动到我们提前存好的 next。一直循环到 cur 走到空此时 pre 停在最后一个节点也就是反转后的新头结点整个反转就完成了。public ListNode reverseList(ListNode head) { ListNode pre null; ListNode cur head; while (cur ! null) { ListNode next cur.next; cur.next pre; pre cur; cur next; } return pre; }3. 链表的中间结点876. 链表的中间结点 - 力扣LeetCode首先我们看到题目如果老老实实先遍历一遍统计长度再走一半距离需要遍历两次链表效率不算最优。我们思考下能不能只用一趟遍历找到中点这里就要用到快慢指针思想。我们准备慢指针 slow 一次走一步快指针 fast 一次走两步。大家想一下快指针速度是慢指针两倍当快指针走到链表末尾的时候慢指针刚好就在中间位置。题目要求偶数节点返回第二个中间点循环条件就写成fast ! null fast.next ! null循环结束slow 就是答案。public ListNode middleNode(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; }4. 链表中倒数第 k 个结点面试题 02.02. 返回倒数第 k 个节点 - 力扣LeetCode首先我们看到这道题单向链表没办法从尾部往前查找。很多人先统计链表总长度再正向走 n-k 步依旧两次遍历。我们思考一趟遍历的方案依旧使用快慢指针。我们先让快指针先走 k 步快慢两个指针中间就隔开了 k 个距离。之后快慢指针同步一起往后移动等到快指针走到 null 的时候慢指针停留的位置正好就是倒数第 k 个结点。public ListNode getKthFromEnd(ListNode head, int k) { ListNode slow head; ListNode fast head; for (int i 0; i k; i) { fast fast.next; } while (fast ! null) { slow slow.next; fast fast.next; } return slow; }5. 合并两个有序链表21. 合并两个有序链表 - 力扣LeetCode首先我们看到题目两个有序链表合并成一条有序链表。两个链表起点都不确定大小头节点不好直接确定。那我们依旧使用虚拟头结点新建 cur 指针用来不断拼接节点。我们同时遍历两条链表每次对比当前两个节点的值把更小的节点接到 cur 后面对应的链表指针向后移动cur 也同步后移。等到其中一条链表遍历完毕直接把剩下另一条链表全部接到 cur 后面整个合并工作就完成了。public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy new ListNode(-1); ListNode cur dummy; while (list1 ! null list2 ! null) { if (list1.val list2.val) { cur.next list1; list1 list1.next; } else { cur.next list2; list2 list2.next; } cur cur.next; } cur.next list1 null ? list2 : list1; return dummy.next; }6. 链表分割链表分割_牛客题霸_牛客网首先我们看到题目需要把链表分成两部分。如果我们在原链表上直接拆改指针非常容易混乱。那我们可以换个思路直接创建两条临时链表一条存放小于 x 的节点一条存放大于等于 x 的节点。我们遍历原始链表逐个节点分到两条链表中。遍历结束之后我们把小数链表的尾部连接大数链表的起点。这里有一个极易踩坑的点大数链表最后一个节点的 next 可能还保留原来的指针如果不置空会形成环形链表一定要加上big.next null最后返回分割后的链表。public ListNode partition(ListNode head, int x) { ListNode smallDummy new ListNode(-1); ListNode bigDummy new ListNode(-1); ListNode small smallDummy; ListNode big bigDummy; ListNode cur head; while (cur ! null) { if (cur.val x) { small.next cur; small small.next; } else { big.next cur; big big.next; } cur cur.next; } big.next null; small.next bigDummy.next; return smallDummy.next; }7. 链表的回文结构链表的回文结构_牛客题霸_牛客网首先我们看到题目判断链表是不是回文。最简单的办法把数值存数组但是占用额外空间。我们追求空间复杂度更低的做法。我们可以拆解成两步先用快慢指针找到链表中点把链表切成前后两半接着把后半段链表反转。之后我们拿两个指针分别从头、反转后的后半段起点开始逐个对比节点的值。只要所有节点数值都相等就是回文链表一旦出现不等直接判定不是回文。public boolean isPalindrome(ListNode head) { if (head null || head.next null) return true; ListNode mid middleNode(head); ListNode right reverseList(mid); ListNode left head; while (right ! null) { if (left.val ! right.val) { return false; } left left.next; right right.next; } return true; } private ListNode middleNode(ListNode head) { ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; } private ListNode reverseList(ListNode head) { ListNode pre null, cur head; while (cur ! null) { ListNode next cur.next; cur.next pre; pre cur; cur next; } return pre; }8. 两个链表的第一个公共结点160. 相交链表 - 力扣LeetCode首先我们看到题目两个链表可能相交找到第一个公共节点。两条链表长度大概率不一样如果直接同步遍历很难同时走到交点。我们想一个巧妙的双指针方法设置 pA、pB 分别遍历两条链表。pA 走完 A 链表之后转头去遍历 B 链表pB 走完 B 链表之后转头遍历 A 链表。大家可以简单推导路径长度两者走过的总路程相等。如果存在公共节点两个指针一定会在交点相遇如果没有交点最后两者同时走到 null循环结束直接返回结果。public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA headA; ListNode pB headB; while (pA ! pB) { pA pA null ? headB : pA.next; pB pB null ? headA : pB.next; } return pA; }总结咱们梳理一下这几道题通用的解题思路大家做题可以优先思考这几个方向。遇到头节点难以处理优先想到虚拟头结点需要一趟遍历寻找特定位置尝试快慢指针需要重组链表可以拆成多条临时链表最后拼接涉及链表逆序链表反转就是常用工具。写链表代码一定要多留意指针会不会形成环、会不会出现断链边界条件一定要想完整。今天面试篇就到这了。诸位共勉
