⭐5.分割链表
题目：
解题思路：
①本题用的双链表的方法，分别写一个A链表和B链表，A链表放值小于X的节点，B链表放值大于X的节点，依次遍历原链表就行了
②不过要注意一个关键点，遍历结束后，我们将 L2 的next指针置空，这是因为当前节点复用的是原链表的节点，而其 指针可能指向一个小于 xx 的节点，我们需要切断这个引用
③最后将两个链表合成一个链表即可 （L1.next指向B.next就可以了）
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode partition(ListNode head, int x) { ListNode headA=new ListNode();//设置一个傀儡节点A，代表A链表 ListNode headB=new ListNode();//再设置一个傀儡节点B，代表B表 ListNode l1 = headA;//局部引用l1 ListNode l2 = headB;//局部引用l2 ListNode cur= head;//局部引用cur while(cur!=null){//遍历原链表 if(cur.val<x){//小于X放A l1.next=cur; l1=l1.next; }else{ //大于X放B l2.next=cur; l2=l2.next; } cur=cur.next;//依次遍历 } l2.next=null;//遍历结束后，我们将 l2 的next指针置空 //这是因为当前节点复用的是原链表的节点，而其指针可能指向一个小于 xx 的节点 //我们需要切断这个引用 l1.next=headB.next;//链接两个链表，A的尾巴指向B的头 return headA.next;//返回A的next，因为第一个节点其实是傀儡节点 //第二个开始才是A链表的头结点 } }
⭐6.删除链表中重复节点（重复节点不保留）
题目：
解题思路：
主要思想就是遍历原链表，将不重复的节点提取出来放到一个新的链表里
①遍历原链表（利用临时变量cur代替头结点）
②创建一个新头结点，代表一个新链表
③判断当前节点与下一个节点是否相同，如果相同则cur往后走一步，不同则将此节点存入新节点
④返回新头结点的下一节点（新头结点其实是傀儡节点，新链表其实是从第二个节点开始的）
public ListNode deleteDuplicates(ListNode head) { ListNode cur = head;//设置临时变量代替头结点遍历原链表 ListNode newHead = new ListNode(-1);//创建一个新头结点代表一个新的链表 ListNode tmp = newHead;//设置临时变量代替新链表的头结点 while (cur != null) {//设置终止条件 if (cur.next != null && cur.val == cur.next.val) { //判断当前节点值是否等于下一个节点 //前提是下一个节点不为null，不然会有空指针导致访问异常 while (cur.next != null && cur.val == cur.next.val) { //这里还需要考虑到有两个以上重复的节点怎么处理 //所以还需要一个while来跳过重复节点 cur = cur.next; } cur = cur.next;//往后多走一步，因为题目要求不需要保留重复节点 } else {//不满足等值条件的点，直接跳过，往后遍历即可 tmp.next = cur; tmp = tmp.next; cur = cur.next; } } //防止最后一个节点值也是重复的 tmp.next = null;//因为cur是原链表的引用，后边还会指向原链表中的节点 //所以要置空，只保留当时cur指向的那个节点 return newHead.next; }
⭐7.判断链表是否是回文结构
题目：
解题思路：
本题首先得了解什么是回文结构，回文结构就是正着读反着读都一样的链表
①快慢指针法找中间节点
②后半段链表反转
③判断两端链表是否相同
④注意考虑链表为偶数的情况
public boolean isPalindrome(ListNode head) { ListNode fast = head; ListNode latter = head; //找中间点 while(fast!=null&&fast.next!=null){//经典的快慢指针法找中间点，就不多bb了 fast=fast.next.next; latter=latter.next; } //后半段反转 ListNode cur=latter.next; while(cur!=null){//经典的反转链表，也不多BB了，具体方法请看第一题 ListNode curNext=cur.next;//设置暂存点 cur.next=latter; latter=cur; cur = curNext; } //判断两段链表是否相同 while(head!=latter){//head从头往后走，latter从后往前走，直到相遇 if(head.val==latter.val){//判断两段链表值是否相等 if (head.next == latter) {//考虑链表为偶数的情况 return true;//偶数链表的情况头结点下一个节点就是latter的时候直接返回true } } else{ return false; } latter=latter.next;//latter依次遍历 head=head.next;//head依次遍历 } return true;//能跳出循环说明，链表符合回文结构，返回true }
⭐8.找出两个链表的第一个公共节点
题目：
解题思路：这里说一种很6P的解法，是leetcode上看到的一个题解
直接将两条路分别拼接在对方末尾，这样两条路便一样长，再从这两条新的路起始点往后比较即可，如下图 节点相同地方一句圈起来，两条链表记住，公共节点指的就是公用一个节点，不是值相同，所以要对比的是地址，蓝色连接代表链表结束换路
①设置两个临时节点节点，分别指向A链表头结点和B链表头结点
②只要这两个临时节点不指向同一个地址，就说明还没走到第一个公共节点
③当临时节点走到一条链表的尾节点时（p1/p2.nextnull）就走另外一条链
④啥时候p1等于p2了，即p1和p2指向同一个地址了==，这个地址就是第一个公共节点的地址，返回其即可
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode p1 = headA, p2 = headB;//设置两个临时节点节点 //分别指向A链表头结点和B链表头结点 while(p1 != p2){ p1 = p1 == null ? headB : p1.next;//p1依次往后遍历，走到尾节点了就走另一条链表 p2 = p2 == null ? headA : p2.next;//p2依次往后遍历，走到尾节点了就走另一条链表 } return p1;//跳出循环了说明找到公共节点了 }
⭐9.判断链表是否有环
题目：
解题思路：
找环其实就是一个追击问题，依旧采取双指针的方法，设置一个快指针一个慢指针，快指针每次走两步，慢指针每次走一步，如果链表有环，快指针和慢指针终究会相遇，因为跑的快的人最终肯定会超跑得慢的人一圈，当他们相遇的时候刚好超了一圈
①设置一个快指针，一个慢指针
②两个指针都指向头结点
③快指针每次走两步，慢指针每次走一步
④如果有环，两个指针一定会在某一时刻相遇，否则无环
public boolean hasCycle(ListNode head) { ListNode fast = head;//设置快指针，指向头结点 ListNode slow = head;//设置慢指针，指向头结点 ListNode cur = head;//设置临时变量代替头结点，用于遍历链表 while(fast!=null&&fast.next!=null ){ fast=fast.next.next;//快指针每次走两步 slow=slow.next;//慢指针每次走一步 if(fast==slow)//快慢指针相遇 return true;//说明有环 } return false;//快慢指针没相遇说明无环 }
⭐10.返回链表开始入环的第一个节点
题目：
解题思路：
我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇如下图所示，设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc
根据题意，任意时刻，fast 指针走过的距离都为slow 指针的 2 倍。因此，我们有
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
有了 a=c+(n-1)(b+c)的等量关系，我们会发现：从相遇点到入环点的距离加上 n-1圈的环长，恰好等于从链表头部到入环点的距离。
因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 tmp它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。
解题步骤：
①利用快慢指针方法找相遇点
②找到相遇点之后，设置临时变量tmp代替头结点，tmp和slow同时移动，直至相遇
③相遇点即为环的呃入口
public ListNode detectCycle(ListNode head) { if(head==null||head.next==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==slow){ ListNode tmp = head;//临时变量代替头结点 while(tmp!=slow){//tmp和slow同时移动 slow = slow.next; tmp = tmp.next; } return tmp;//tmp和slow相遇的节点就是环的入口点 } return null; }
