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;


     }