当前位置：首页 > news >正文

链表_必会面试题2

news 2026/5/12 17:13:52

目录
一、链表分割
二、求公共节点
三、给定⼀个链表，判断链表中是否有环。
四、链表是否有环2
力扣链表刷题链接：

一、链表分割

以给定值x为基准将链表分割成两部分，所有小于x的结点排在⼤于或等于x的结点之前。

OJ链接：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

看完题目后，其实可以很明显地明白思路，也就是给定一个数字x，比x小的放一边，大于等于x的放一边，组成两个链表后，再将两个链表链接到一起。

比如给定一个x=25，就可以分成以上的两个链表。

来看代码：

public class Partition { public ListNode partition(ListNode pHead, int x) { // write code here if(pHead == null) { return null; } ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; ListNode cur = pHead; while(cur != null) { if(cur.val < x) { //小于x if(bs == null) { //说明这是第一次进行插入 bs = be = cur; }else { be.next = cur; be = be.next; } }else { //大于等于x if(as == null) { as = ae = cur; }else { ae.next = cur; ae = ae.next; } } cur = cur.next; } //第一个段 没有数据 if(bs == null) { return as; } be.next = as; if(as != null) { ae.next = null; } return bs; } }

二、求公共节点

输⼊两个链表，找出它们的第⼀个公共结点。

OJ链接：

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

如图所示，思路如下：

也就是：

分别求2个链表的长度 len1 len2 = len —— len 有可能是负数
让长的链表先走差值步，最后一起走 —— 哪个链表长
直到相遇

有了思路后，来看代码：

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pl = headA; ListNode ps = headB; //这里保存headA这个链表的长度 int lenA = 0; //这里保存headB这个链表的长度 int lenB= 0; //分别求长度 while( pl != null) { lenA++; pl = pl.next; } while( ps != null) { lenB++; ps = ps.next; } pl = headA; ps = headB; //计算差值 int len = lenA - lenB; if(len < 0) { pl = headB; ps = headA; len = lenB - lenA; } //pl一定指向最长的链表 ps一定指向最短的链表 len一定是正数 while(len != 0) { pl = pl.next; len--; } while(pl != ps) { pl = pl.next; ps = ps.next; } return pl; } }

三、给定⼀个链表，判断链表中是否有环。

OJ链接：https://leetcode.cn/problems/linked-list-cycle/description/

如何理解思路呢？

如图所示，假如链表有一个环，那么直接使用快慢指针法：

每次让fast走两步，slow走一步，那它们的差值就是一步

一个环的极限长度就是1；

那么当它们差值唯一时，只要有环，那么一定会相遇！

来看简单的代码：

public class Solution { public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { return true; } } return false; } }

四、链表是否有环2

给定⼀个链表，返回链表开始⼊环的第⼀个节点。如果链表⽆环，则返回NULL

OJ链接：

https://leetcode.cn/problems/linked-list-cycle-ii/description/

思路可参考第三点，基本一样的思路，此处不赘述了。

代码：

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } //1.没有环 2.有环（遇到break结束） if (fast == null || fast.next == null) { return null;//没有环 } fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return slow; } }