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是不是nullif (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;}