前言
上一篇
欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
目录
前言
链表分割
链表的回文结构
相交链表
环形链表
链表分割
编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。OJ链接
1.定义一个节点cur遍历原链表,创建两个新链表B和A，用于放小于x和大于x的，最后将这两个链表连接构成一个新链表。这两个链表分别创建两个节点bs be和as ae,bs作为B链表的头节点,be用于添加节点，as和ae同理
2.比较每个节点的val与x的大小
若val<x，则该节点放在新链表B中
be.next=cur;be=be.next;其中要注意第一次插入be=bs=cur;
若val>x，则该节点放在新链表A中
ae.next=cur;ae=ae.next;其中要注意第一次插入ae=as=cur;
3.注意：
最后一个节点的next，没有null
要判断全部小于x，或全部大于等于x的情况（即遍历完原链表发现B链表为空或者A链表为空）
发现B链表为空 直接返回A链表 return as;
4.拼接
将B和A链表拼接，return bs;
public class Partition { public ListNode partition(ListNode pHead, int x) { if(pHead==null){ return null; } // write code here ListNode bs=null; ListNode be=null; ListNode as=null; ListNode ae=null; ListNode cur=pHead; while(cur!=null){ if(cur.val<x){ if(bs==null){ be=bs=cur;//第一次插入 }else{ be.next=cur; be=be.next; } cur=cur.next; }else{ 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链接
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构,给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
1.找中间节点
快慢指针法（在上一篇有详细讲到），此时fast在走完了链表，slow在中间
2.反转中间节点以后的部分 (在上一篇也有详细讲到）
cur=slow.next;while(cur!=null){curN=cur.next;cur.next=slow;slow=cur;cur=curN;}
反转链表后slow一定是尾节点
3.对比前后的val值
cur=slow.next
不能使用fast遍历（fast不一定是尾节点，当链表个数为偶数时，fast为空），所以用slow
注意：
偶数节点时，head和slow没有办法相遇
//判断偶数情况 if(head.next==slow){ return true; }
public class PalindromeList { public boolean chkPalindrome(ListNode head) { // write code here //空链表也是回文的 if(head==null){ return true; } //1.找中间节点 ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } //2.反转中间节点之后的链表 ListNode cur=slow.next; while(cur!=null){ ListNode curN=cur.next; cur.next=slow; slow=cur; cur=curN; } //3.对比head和slow的val值 while(head!=slow){ if(head.val!=slow.val){ return false; } //判断偶数情况 if(head.next==slow){ return true; } head=head.next; slow=slow.next; } return true; }}相交链表
输入两个链表，找出它们的第一个公共结点。OJ链接
链表相交后，形成Y结构链表，如图题目要求是找出值为60的节点
1.分别求2个链表的长度，求出差值x
2.让长的先走x步
3.然后一起走，直到相遇
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //假设p1是长链表 ListNode p1=headA; ListNode p2=headB; int lenA=0; int lenB=0; while(p1!=null){ p1=p1.next; lenA++; } while(p2!=null){ p2=p2.next; lenB++; } //要重新让p1和p2指向头节点 p1=headA; p2=headB; int len =lenA-lenB; if(len<0){ p1=headB; p2=headA; len=lenB-lenA; } //走完上面代码后p1一定是最长的链表 //让长链表先走len步 for(int i=0;i<len;i++){ p1=p1.next; } //一起走 while(p1!=p2){ p1=p1.next; p2=p2.next; } if(p1==null){ //如果两个引用都为空，证明不相交，返回null 不写也不会报错 return null; } return p1; }}环形链表
给定一个链表，判断链表中是否有环。 OJ链接
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
fast走一步，slow走两步，若相遇，则有环
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; }}
