目录

前言：

1.链表分割

2.相交链表

 3.环形链表

 4.环形链表 II

---

前言：

数据结构想要学的好，刷题少不了，我们不仅要多刷题，还要刷好题！为此我开启了一个必做好题锦集的系列，每篇大约5题左右。此为第二篇选择题篇，该系列会不定期更新敬请期待！

---

1.链表分割

 代码：

public class Partition {public ListNode partition(ListNode head, int x) {if(head==null){return null;}ListNode cura1=null;ListNode curb1=null;ListNode cura2=null;ListNode curb2=null;ListNode cur=head;while (cur!=null){if(x>cur.val){if(cura1==null){cura1=cur;curb1=cur;}else{curb1.next=cur;curb1=curb1.next;}}else{if(cura2==null){cura2=cur;curb2=cur;}else{curb2.next=cur;curb2=curb2.next;}}cur=cur.next;}if(cura1==null){return cura2;}curb1.next=cura2;if(curb2!=null){curb2.next=null;}return cura1;}
}

解析：

示例1：

（1）

 （2）

（3） 

（4） 

示例2： 

示例3：

（1）

 （2）

---

2.相交链表

160. 相交链表https://leetcode.cn/problems/intersection-of-two-linked-lists/ 

 

 

 方法1

代码：

    public ListNode getIntersectionNode(ListNode head1, ListNode head2) {if (head1==null||head2==null){return null;}int size1=size(head1);int size2=size(head2);int size=size1-size2;//设长链表为head1，短链表为head2if(size<0){size=-1*size;ListNode tmp=head1;head1=head2;head2=tmp;}while(size>0){size--;head1=head1.next;}while(head1!=head2){head1=head1.next;head2=head2.next;}return head1;}public int size(ListNode head){int count=0;while(head!=null){count++;head=head.next;}return count;}

解析：

（1）

（2） 

 

（3） 

 方法2

代码：

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;
}

解析：

pA走过的路径为A链+B链

pB走过的路径为B链+A链

pA和pB走过的长度都相同，都是A链和B链的长度之和，相当于将两条链从尾端对齐，如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。

---

 3.环形链表

环形链表https://leetcode.cn/problems/linked-list-cycle/

 

 

代码：

    public boolean hasCycle(ListNode head) {if(head==null){return false;}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;}

解析：

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表 带环则一定会在环中相遇，否则快指针率先走到链表的末尾。

当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指 针的，即相遇。

扩展问题 

小结：

走3步，在2个节点的环中实际上是走了一个周期多一步，当走1步的进入环与 走3步的没有相遇，之后就无法相遇，因为速度相同。

---

 4.环形链表 II

142. 环形链表 IIhttps://leetcode.cn/problems/linked-list-cycle-ii/

 

 代码：

    public ListNode detectCycle(ListNode head) {if(head==null){return null;}ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(fast == slow) {break;}}if(fast == null || fast.next == null){return null;}slow=head;while (slow!=fast){fast = fast.next;slow = slow.next;}return slow;}

解析：

---

 

以上为我个人的小分享，如有问题，欢迎讨论！！！ 

都看到这了，不如关注一下，给个免费的赞