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