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

这篇具有很好参考价值的文章主要介绍了力扣链表oj面试题,保姆级图解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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


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


目录

1. 链表分割

 1)代码实现

 2. 链表的回文结构

2)代码实现

3.相交链表

3)代码实现

 4.环形链表

4)代码实现


1. 链表分割

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

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

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

 力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

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

 力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

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

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

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

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

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

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

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

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

最后结果就如下图: 

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

你就发现问题了,我们的尾节点不是为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. 链表的回文结构

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

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

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

奇数情况下的反转:

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

最后让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;
    }
}

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

如图所示,当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;
    }
}

 力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

3.相交链表

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言 

那么这题应该怎么做呢?

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

当然,有时候还会有这种情况:这也是一种相交!

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言 

那么我们可不可以让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;
    }
}

 力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

 4.环形链表

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

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

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

所以我们要确保二者相遇,那么我们就定义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;
    }
}

力扣链表oj面试题,保姆级图解,算法,java,链表,数据结构,开发语言

希望对大家有所帮助,感谢阅读!!!文章来源地址https://www.toymoban.com/news/detail-817410.html

到了这里,关于力扣链表oj面试题,保姆级图解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 链表习题-力扣oj (附加思路版)

    LCR 140. 训练计划 II https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/         给定一个头节点为  head  的链表用于记录一系列核心肌群训练项目编号,请查找并返回倒数第  cnt  个训练项目编号。 思路:双指针, 快指针先走cnt步 然后快慢指针同时向前走,当快指

    2024年03月09日
    浏览(78)
  • 顺序表、链表刷题指南(力扣OJ)

    目录 前言 题目一:删除有序数组中的重复项 思路: 题解: 题目二:合并两个有序数组 思路: 分析: 题解: 题目三:反转链表 思路: 分析: 题解:  题目四:移除链表元素 思路一: 分析: 题解: 思路二: 分析: 题解: 总结         无论是面试准备还是日常编码

    2024年02月14日
    浏览(39)
  • 【Java数据结构 -- 队列:队列有关面试oj算法题】

    只允许在一端进行插入数据操作,在另一端进行删除数据操作得特殊线性表,队列是 先进先出 ,入队:进行插入操作得一端称为 队尾(rear) ,出队:进行删除操作的一端称为 队头(front) 。队列Queue是个接口, 底层通过链表实现的 。 boolean offer(E e) – 入队列 E poll() – 出队

    2024年01月25日
    浏览(48)
  • 数据结构刷题篇 之 【力扣二叉树基础OJ】详细讲解(含每道题链接及递归图解)

    有没有一起拼用银行卡的,取钱的时候我用,存钱的时候你用 难度等级:⭐ 直达链接:相同的树 难度等级:⭐ 直达链接:单值二叉树 难度等级:⭐⭐ 直达链接:对称二叉树 难度等级:⭐⭐⭐ 直达链接:二叉树的前序遍历 难度等级:⭐⭐⭐⭐ 直达链接:另一颗子树 注:

    2024年04月16日
    浏览(80)
  • 力扣题解24. 两两交换链表中的节点(图解递归和双指针)

    题目描述: 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 示例 1: 示例 2: 示例 3: 提示: 链表中节点的数目在范围 [0, 100] 内 0 = Node.val = 100 方法一:递归 代码解析 这

    2024年01月15日
    浏览(47)
  • (C语言版)力扣(LeetCode)数组相关面试题OJ题解析

    给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过: ★更

    2024年02月03日
    浏览(52)
  • 链表经典算法OJ题目

    直接在原链表里删除val元素,然后让val前一个结点和后一个节点连接起来。 这时我们就需要3个指针来遍历链表: pcur  —— 判断节点的val值是否于给定删除的val值相等 prev ——保存pcur的前一个节点,为删除节点后,连接pcur之后的节点做准备 del —— 保存pcur之后的一个节点

    2024年04月26日
    浏览(34)
  • 【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析)

    还不清楚链表的码喵们可以看看前篇关于链表的详解 既然已经懂得了链表该如何实现,那么现在就趁热打铁开始练习!这里给码喵们整理了相对不错的一些OJ题来练习  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 思路:遍历整个表,访问每个表的值并且删除再将nex

    2024年02月22日
    浏览(51)
  • 力扣面试题02.07.链表相交

    原题链接:力扣面试题02.07.链表相交 思路 两个长度不确定是否一致的链表,如果 相交,那么一定是有一个链表结点相同 ,注意 不是值相同而是结点相同 ,也就代表了是 需要指针是相同的才行 根据图可以得出, 相交后的结点都是一致的,那么需要做的就是把两个链表长度

    2024年02月06日
    浏览(39)
  • 【数据结构与算法】手撕链表OJ题

    给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 思路一 :一种比较普遍的方式,边遍历边找不同。我们可以通过定义两个指针,一个指向头节点,一个置为NULL。当遇到值为相同的时候,直接跳过去。指向下一位

    2024年02月10日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包