LinkedList和链表之刷题课(下)
1. 给定x根据x把链表分割,大的结点放在x后面,小的结点放在x前面
题目解析:
注意此时的pHead就是head(头节点的意思)
基本上就是给定一个链表,我们根据x的值来把这个链表分成俩部分,大的那部分放在x后面,小的那部分放在x前面,并且我们不能改变链表本来的顺序,比如下面的链表,我们先找到的15,就不能把23放在15前面,差不多就是找到一个插一个.
我们定义cur指向当前的head结点,我们再定义bs,be,as,ae分别代表分割成的俩部分的头和尾,在一开始,我们cur指向的第一个结点,我们be和bs或者as,ae都指向第一个结点.
当我们安置好第一个结点的时候,我们就开始对后面结点进行操作,此时我们的as和bs不会动,一直指向第一个结点,而我们的ae,be就会一直指向最后一个结点,会不断的跟新,比如,33大于x,应该放在右边,as.next = cur;as = as.next;因为cur的跟新在if和else都有,因此我们直接合并成一句,放在循环内部,if和eles外部,cur = cur.next;
但是,这里有一个地方,就是我们需要判断一下极端情况,比如只有一个半区的情况也就是下图.
如果,我们不把ae置空我们就会出现这种情况,我们ae会指向一个结点,然后形成一个死循环
整体代码:
//TODO ，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
//链表分割
public ListNode partition(ListNode pHead, int x) {
//先判断pHead是不是null
if (pHead == null) {
return null;
}
//设置俩个链表的开头和结尾,分别进行尾插法
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
//遍历链表
while (cur != null) {
//判断cur和x的值
if (cur.val < x) {//如果<x那就放在bs和be里面
if (bs == null) {//如果是第一个结点
be = cur;
bs = cur;
} else {//be永远指向的是最后一个结点
be.next = cur;
be = be.next;
}
} else {//如果<x那就放在bs和be里面
if (as == null) {//如果是第一个结点
ae = cur;
as = cur;
} else {//be永远指向的是最后一个结点
ae.next = cur;
ae = ae.next;
}
cur = cur.next;
}
}
//但是不一定是有左右俩边的,可能只有一边
if(bs == null){
//第一个区间没有数据
return as;
}
// if(as == null) {
// //第二个区间没有数据
// return bs;
// }
//直接合并为一个
//链接俩个链表,第一个区间有数据
be.next = as;
//左右都有数据的情况,要把ae置为空不然这玩意会报空指针异常
if(as != null) {
//第二个区间有数据
ae.next = null;
}
return pHead;
}2. 链表的回文结构
题目解析:
给我们一个链表,我们需要判断是不是回文链表,也是就从中间为界限,从后往前和从前往后对应的结点的val要一致,直到相遇为止.
基本上就是分为俩步骤:1> 找到中间结点 2> 改变链表结构((从中间开始直到最后,让链表翻转) 3> 一次比较俩端的结点值.
我们先进行第一步,找到中间结点,我们使用快慢指针来找,fast每次走俩步,slow每次走一步,当退出循环的时候,slow指向的位置就是中间位置.
我们进入第二步骤,把链表进行翻转,我们定义cur指向slow的下一个结点,curNext指向cur的下一个结点,当cur != null 的时候我们就把cur.next = slow,然后更新slow,slow = cur;再更新cur,cur = curNext;
第三步:从前往后从后往前分别比较,此时我们要考虑偶数结点的情况下,我们会产生偶数个结点的时候判断失败,主要原因和解决方法如图,我们只要判断head.next是否和slow指向的结点相同即可
整体代码:
public boolean chekPalindrome() {
if (head == null || head.next == null) {
return true;
}
ListNode fast = head;
ListNode slow = head;
//1. 先找到中间位置
while (fast != null && fast.next != null) {//注意这里分奇偶节点数
fast = fast.next.next;//这个可能造成fast后面就是一个null的情况,因此判断条件不能换,不然会空指针异常
slow = slow.next;
}
//出来之后slow就是中间位置
//2. 翻转
ListNode cur = slow.next;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//此时slow在最后,不用fast的原因是,当结点为偶数个的时候fast会移动到链表外面
//3. 从前到后,从后到前
while (head != slow) {
if (head.val != slow.val) {
return false;
}
if (head.next == slow) {
return true;//判断如果是偶数情况下
}
head = head.next;
slow = slow.next;
}
return true;
}3. 输入俩个链表,找出它们的第一个公共结点
题目解析:
现在我们有俩个相交链表(不为空),我们要找到他们的公共结点,并且返回公共结点.如下图的情况.整体就分为四步:
1. 分别求长度. 2.最长的走差值步. 3. 同时走. 4. 相遇的就是交点
因为俩个链表的长度我们不确定,因此我们不能够同时走,然后边走边比较.我们应该让长的链表先走.此时我们设置pl和ps分别指向headA和headB.(pl指向的是长的,ps指向的是短的,现在此刻先默认headA是长的),然后我们求出headA和headB链表的长度.len1,len2.当pl和ps进行完了遍历操作之后,他们已经走完了链表为null了,所以我们需要更新他们,让他们指向头.然后我们先让len=len1-len2,判断len是不是大于0,如果大于0,我们就知道headA大于headB,我们就不需要更改pl和ps.如果小于0,我们就需要改变pl和ps的指向,并且让len = len2-len1;
然后我们让长的链表先走len步,也就是当pl!=null的时候,我们一直让pl=pl.next;
我们再让pl和ps指向的链表同时走.直到pl==ps为止跳出循环
但是跳出循环的条件其实还有一种情况,当pl和ps一样长并且没有交点的时候,我们就需要判断pl==null;如果满足就返回null
整体代码:
public ListNode getIntersectionNode(ListNode headA,ListNode headB) {
//1.分别求俩个链表的长度
//pl指向最长的,ps指向最短的
ListNode pl = headA;
ListNode ps = headB;
int len1 = 0;
int len2 = 0;
while (pl != null) {
len1++;
pl = pl.next;
}
while (ps != null) {
len2++;
ps = ps.next;
}
//重新到头
pl = headA;
ps = headB;
int len = len1 - len2;
if(len < 0) {
pl = headB;
ps = headA;
len = len2 - len1;
}
//2.最长的走差值步
while (len != 0) {
pl = pl.next;
len--;
}
//3.一起走
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
//如果链表很短,而且一样长,不会相遇也会跳出循环
if(pl == null) {
return null;
}
return pl;
}4. 给定一个链表,判断链表是否有环
题目解析:
一个链表有环,差不多就是下面这个情况,我们的最后一个结点指向的是前面的结点,然后形成一个环.
此刻我们使用快慢指针,fast = head;slow = head;每次fast走俩步,slow走一步,只要我们的fast比slow快,先进入环,那么我们的fast和slow一定会在环里面相遇.
我们while的判定条件不能是fast!=slow;因为如果没有环的话,fast会一直往下走,此时到最后一个结点的时候fast.next.next就会导致空指针异常.我们只能是把fast != null;fast.next != null 作为判定条件,保证没有环的情况.
整体代码:
//TODO 求环的入口点
public ListNode detectCycle () {
if (head == null) {
return null;
}
//设定快慢指针
ListNode fast = head;
ListNode slow = head;
//fast走俩步,slow走一步
// while (fast != slow) {//TODO 这样写会空指针异常
// fast = fast.next.next;
// slow = slow.next;
// }
while (fast != null && fast.next != null) {//TODO 这样写会空指针异常
//有可能为环,有可能为直线
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
//此刻相遇了
break;
}
}
//无环
if(fast == null || fast.next == null) {
return null;
}
//有环
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}5.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
题目解析:
我们要找到开始入环的第一个结点如图
首先找到相遇结点,这个在第4题就解决了,然后我们更新slow,最后让slow和fast不断一直走,直到相遇为止,此时就是入口结点.
整体代码:
//TODO 求环的入口点
public ListNode detectCycle () {
if (head == null) {
return null;
}
//设定快慢指针
ListNode fast = head;
ListNode slow = head;
//fast走俩步,slow走一步
while (fast != null && fast.next != null) {//TODO 这样写会空指针异常
//有可能为环,有可能为直线
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
//此刻相遇了
break;
}
}
//无环
if(fast == null || fast.next == null) {
return null;
}
//有环
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}