前言
上一篇
欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
目录
前言
链表分割
链表的回文结构
相交链表
环形链表
链表分割
编写代码，以给定值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;
}
}
