力扣链表oj面试题，保姆级图解

 少年也识愁滋味，写作码文挠破头。

 前言：期末考试临近，博主也在备战期末，自上篇链表oj面试题博客的发布后，近一个月没有新文出炉了，博主跟小伙伴们一样都在好好复习呢！！不知道诸位小伙伴考的如何，在这里博主给大家伙拜个早年啦！同时也很感谢各位小伙伴们的支持！！新年新气象，2024一起加油吧！！！

目录

1. 链表分割

 1）代码实现

 2. 链表的回文结构

2）代码实现

3.相交链表

3）代码实现

 4.环形链表

4）代码实现

1. 链表分割

题目：编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
首先这有个链表，题目没有说是有序的，所以我们以乱序的链表为例：

假设x = 30,那么根据题意（所有小于x的结点排在大于或等于x的结点之前），最后链表的效果如下：

 我们来看看力扣的题目描述：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

题目分析：他要求我们不能改变原来的数据顺序，我们看最上面那张图，在x = 30的情况下，23和12同时小于30，但是23在12的前面，所以在效果图里，23还是在12之前，大于30的部分，也保持了45、34、56的顺序，他们的相对顺序没有改变。最后让我们返回一个排列后的链表的头指针，说明让我们返回一个新的链表

解题思路：这题将链表分割成两部分，一部分小于x，一部分大于等于x，我们可以在这两条链表的头尾都加上一个标记，如下图所示：

当我们把小于x的放到了左边的链表，大于等于x的都放到了右边的链表，我们再把 be 和 as 连接起来，然后返回bs，是不是就解决了？

我们可以定义一个cur来遍历我们的链表，如果cur小于x，就放左边那个小链表，如果cur大于等于x，就放右边那个小链表，如下图：

 注意：我们要保持顺序相同，所以23一定要在12前面，45一定要在34、56前面，所以我们应该用尾插法来实现

当我们尾插各小链表的第一个数时，这个数既是各个小链表的头，又是各个小链表的尾，所以我们把bs和be，as和ae同时放到各自的数下面，为什么这么做呢？如果我们不把be和ae放到这里，那么我们在插第二个数的时候怎么找到这条链表的尾部进行尾插呢？如上图：

当我们进行尾插时候，就不需要遍历链表了，因为我们的be永远指向第一条链表的最后一个节点，所以我们可以直接让be.next = cur; 然后让 be 往后走 ，如下图：

当我们重复尾插完后，让 be.next = as ; 然后返回 bs 即可解决题目，如下图：

这题还需要考虑几个特殊的点：

1.pHead是否为空？也就是说给的链表是不是空表

2.能确定一定存在小于x的值或者大于等于x的值吗？也就是说不一定存在两个小链表都存在的情况，如果没有小于x的值，我们最后让两个小链表合并，就会发生空指针异常 

所以我们先要判断链表是否为空

if(pHead == null) {return null;}

第二个问题，我们只需要在最后合并链表时候添加一个If判断就可以了

if(bs == null) {
    return as;
}
be.next =as;

 这样就解决问题了吗？其实还有个非常隐形的问题：假设最后一个数字为6，如下图：

那么我们尾插完后应该如下图：

这个时候再通过下面这段代码：

if(bs == null) {
    return as;
}
be.next =as;

最后结果就如下图： 

你就发现问题了，我们的尾节点不是为null，力扣网无法校验答案，所以在第二个小链表有数据时应该分为两种情况：

1.ae == null; 

2.ae != null; 

所以我们需要添加一个判断：

if(as != null) {
    ae.next = null;
}

 这样不管ae是否为空，我们都手动置为空，就可以解决这个问题。

 1）代码实现

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead == null) {return null;}
        ListNode cur = pHead;

        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        //使用cur遍历所有节点
        while(cur != null) {
            if(cur.val < x) {
                if(bs == null) { //判断是否第一次插入节点
                    bs = cur; //这个过程相当于插入第一个节点
                    be = cur;
                }else {
                    be.next = cur;
                    be = be.next; //或者be = cur;
                }
            }else {
                //大于等于x
                if(as == null) {
                    as = cur; //这个过程相当于插入第一个节点
                    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;
    }
}

 2. 链表的回文结构

 首先我们要明白什么是回文结构，如下图所示，从前往后读，跟从后往前读是一样的。

思路一：这里总会有人投机取巧，把链表遍历一遍放到数组，然后看这个数组是不是回文的，但是要注意一个点，题目要求时间复杂度O(n)，额外空间复杂度O(1)。所以这种方式不可取。

思路二：还有的人会这么想，在头节点定义一个指针，在最后一个节点定义一个引用，然后让他们往中间走，每走一步比较一次二者是否相等，但他们走到中间值都一样时，这就是个回文结构，这是个不错的思路，但是这是个单向链表，不是双向链表，所以这种方式也有问题。

解题思路：其实我们可以改进一下思路二，先找到这个链表的中间节点，然后把中间节点的后面部分全部翻转，如下图：

接下来就简单了，我们在头节点定义一个指针，最后一个节点定义一个引用，然后让他们两个往中间走，完成这个过程，那就是回文结构了，其实这题所运用的方法在上篇文章中已经讲过了，换汤不换药，就看小伙伴们还记不记得了。先在头节点位置定义一个slow和fast，fast一次走两步，slow一次走一步，节点为偶数个时，当fast.next指向null的时候，slow就是中间节点，如下图：

当fast指向null时候，slow就是中间节点。如下图：

奇数情况下的反转：

我们首先在slow的下个节点定义一个cur，我们要翻转这个cur指向slow这个中间节点，先要记录下来cur的next域，不然会丢失cur后面的节点，所以我们在cur的下一个节点位置定义一个curNext,如下图所示：

然后让cur指向slow，便完成了这一节点的翻转，如下图一：

接着让slow指向cur,cur指向curNext，cueNext指向下一个节点，然后重复上一部分的操作，进行该节点的翻转，如下图所示：

改完之后，slow指向cur，cur指向curNext，现在我们可以看到这个链表翻转完了

最后让head和slow同时向中间遍历，注意不要拿fast遍历，因为在偶数个节点的情况下，fast为空，注意上图博主的值没有修改，所以这个链表不是回文结构，但是思路是没有问题的。

偶数的代码实现：

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        if(head == null) {
            return true;
        }
        //1.找中间节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.翻转
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3.前后遍历
        while(slow != head) {
            if(slow.val != head.val){
                return false;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;
    }
}

接下来就是偶数情况了： 其实偶数情况很简单，我们只需要添加一小段代码即可解决问题

如图所示，当head与head的下一个节点相同的时候即可

if(head.next == slow) {
    return true;
}

2）代码实现

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        if(head == null) {
            return true;
        }
        //1.找中间节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.翻转
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3.前后遍历
        while(slow != head) {
            if(slow.val != head.val){
                return false;
            }
            //偶数情况
            if(head.next == slow) {  //这里的if不能与上面的if调换位置
                                     //一定是先判断值！
                return true;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;
    }
}

3.相交链表

首先，相交链表是x形还是y形？为什么？如果是x形的，那相交的这个结点就有两个next域了，所以相交链表是y形的！两个链表如下图：

我们只需要把值为10 的这个节点指向第一个链表里的任意一个节点，他们便相交了，如下图

那么这题应该怎么做呢？

解题思路：我们观察上图，可以发现其实相交点之后的节点其实都是一样的，也就相交点前是不一样的。 两个链表相交前的节点都是三个，我们可不可以让两个链表同时走？当他们走到相同的节点时，这个节点就是相交节点。

当然，有时候还会有这种情况：这也是一种相交！

那么我们可不可以让headA先走上一步，然后再和headB一起走？那么话说回来，我们怎么知道headA相交节点前有三个节点，headB相交节点前有两个节点呢？其实这个问题不难解决，因为相交链表是个y字形，headA所在的链表有6个节点，headB所在的链表有5个节点，而二者相交节点之后的节点都是一样的，所以二者的长度差一定差在相交节点前面！

所以解决这题，1.要求长度；2.要走差值步，然后一起走，相遇时就是相交节点

 那么我们接下来求长度：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1.求长度
        int lenA = 0;
        int lenB = 0;
        while(headA != null) {
            lenA++;
            headA = headA.next;
        }
        while(headB != null) {
            lenB++;
            headB = headB.next;
        }
        int len = lenA - lenB;
    }
}

这么求有没有问题？我们怎么知道lenA和lenB谁大？len会不会等于负数？所以我先定义pl和ps，分别让他们指向较长的链表和较短的链表，最后让pl➖ps得到len，这时候len就是正数了。所以这里len的求值会麻烦点：

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1.求长度
        int lenA = 0;
        int lenB = 0;
        ListNode pl = headA;//pl永远指向较长的链表，
        ListNode ps = headB;// ps永远指向较短的链表
        while(pl!= null) {
            lenA++;
            pl = pl.next;
        }
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
    }

3）代码实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1.求长度
        int lenA = 0;
        int lenB = 0;
        ListNode pl = headA;//pl永远指向较长的链表，
        ListNode ps = headB;// ps永远指向较短的链表

        while(pl!= null) {
            lenA++;
            pl = pl.next;
        }
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;

        int len = lenA - lenB;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }

        //2.让pl先走len步
        while(len != 0) {
            pl = pl.next;
            len--;
        }

        //3.一人走一步
        while(pl != null && ps != null && pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == ps && pl == null) {
            return null;
        }
        return pl;
    }
}

 4.环形链表

 回环问题，其实是个数学问题！我们在一个回环链表中，可以定义一个fast和slow，让fast走快点，slow走慢点，当他们到一定距离就会相遇，当他们相遇，就说明这个链表是回环的，本题其实最主要是个思维问题，代码实现是很简单的。当我们让fast一次走两步，slow一次走一步时候这种时候两个人就不会错过，为什么呢？这就相当于如下图两个人在跑圈，极限情况下，slow跑完一圈，两人就已经相遇了!我们根据下图发挥想象，不难看出这个过程：slow跑到四分之一圈的时候，fast已经跑完二分之一圈了，当slow跑到二分之一圈时候，fast已经跑完一圈了，当slow跑完一圈的时候，fast也刚好跑完两圈，这个时候两个人就相遇了。所以在一个走一步，一个走两步的情况下是不会错过的！

 那么，一个走两步，一个走三步会如何？根据下图，不难想象出，当二者在同一起点时候，他们会错过，当他们不在一个起点时候，二者会相遇

所以我们要确保二者相遇，那么我们就定义fast一次走两步，slow一次走一步 

4）代码实现

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;
    }
}

希望对大家有所帮助，感谢阅读！！！