链表_必会面试题2

目录一、链表分割二、求公共节点三、给定⼀个链表判断链表中是否有环。四、链表是否有环2力扣链表刷题链接一、链表分割以给定值x为基准将链表分割成两部分所有小于x的结点排在⼤于或等于x的结点之前。OJ链接https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId8tqId11004rp2ru/activity/ojqru/ta/cracking-the-coding-interview/question-ranking看完题目后其实可以很明显地明白思路也就是给定一个数字x比x小的放一边大于等于x的放一边组成两个链表后再将两个链表链接到一起。比如给定一个x25就可以分成以上的两个链表。来看代码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给定⼀个链表返回链表开始⼊环的第⼀个节点。如果链表⽆环则返回NULLOJ链接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; } }力扣链表刷题链接链表 - 力扣LeetCode全球极客挚爱的技术成长平台多刷题画图思考写代码调试