力扣链表OJ面试题,那些你不懂的全新版本解法

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

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

孤独的时候看世界更清晰


 前言

数据结构的逻辑性是非常强的,所以单单看代码很难搞懂,这里博主对每一道题目都进行了非常细致的图文详解,每一道题目都是非常经典的面试OJ题,每一道题我都附上了对应的力扣链接,本文主要是较为简单的题目,比较难的题目将会在下一篇博客中为大家讲解,希望对大家有所帮助,谢谢!!


目录

1. 移除链表元素

 1)总代码

2. 反转链表

 2)总代码

3. 链表的中间结点

3)总代码 

4. 链表中倒数第k个结点

4)总代码   

 5. 合并两个有序链表 

 5)总代码


1. 移除链表元素

题目:删除链表中等于给定值 val 的所有节点 

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

假设我们要删除val=45的节点,那么我们首先要定义一个prev和cur,让prev指向第一个节点,cur指向第二个节点,然后我们判断cur的val是不是45?如果等于那么

prev.next = cur.next; 

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

这样便完成了该节点的删除,该节点就会被回收 

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构 

接着我们便让cur往后面走一步,但是prev不能动,原因是为了防止下个节点依旧是45,当下个节点不是我们要删除的数时,就让prev向前走,使cur和prev处于同一位置(如下图1),然后再让cur往后走(如下图2)

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

所以我们这里要分两种情况,一种是下个节点是我们要删除的数,另一种是下个节点不是我们要删除的数

while(   ) { 
    if(cur.val == val) {
    prev.next = cur.next;
        cur = cur.next;
    }else {
        prev = cur;
        cur = cur.next;
}

 当我们走到0x36这个节点,发现是45,满足我们上述代码的if条件 

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 走到这里我们自然而然知道了while()的条件,那就是 cur != null ,为什么呢?当走到这一步时候,cur所处的节点56不等于45,所以执行else里面的代码

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

这样便把所有的45删掉了,这个时候我们return head即可,但是我们没有考虑到头节点是不是45的问题,所以我们还要完善,我先把上述过程进行代码实现:

public ListNode removeElements(ListNode head, int val) {
    ListNode prev = head; //prey表示当前可能要删除的节点的前驱
    ListNode cur = head.next; //cur表示当前可能要删除的节点

    while(cur != null) {
        if(cur.val == val) {
            prev.next = cur.next; 
            cur = cur.next;
        }else {
            prev = cur;
            cur = cur.next;
        }
    }
    //除了头节点,其他都删除完成了
}

到了这一步,除了头节点我们都删除完了,对于头节点的处理,其实很简单:

if(head.val == val) {
    head = head.next;
}

但是如果我们要在代码开始就先把头节点处理掉,这种情况的话需要加个循环,防止第一第二个节点都是我们要删除的

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 1)总代码

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return null;
        }
        ListNode prev = head; //prey表示当前可能要删除的节点的前驱
        ListNode cur = head.next; //cur表示当前可能要删除的节点

        while(cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
            //除了头节点,其他都删除了
            if(head.val == val) {
                head = head.next;
            }
        }
        return head;
    }
}

2. 反转链表

题目:反转一个单链表 

 这道题要我们做的,其实就是头变尾,尾变头,最终实现下图的效果

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

总思路:将头节点置为空 ,然后对后续的节点都进行头插,因为头插法本身就可以将链表翻转

具体解决操作:定义cur指向当前需要翻转的节点

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 在这里我们可以顺带处理 空表 以及 表里只有一个节点 的情况

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) {return head;}
        if(head.next == null) {return head;}
        ListNode cur = head.next;
        head.next = null;


    }
}

这时候 头节点 为空,我们对 cur 进行头插法,注意:在头插前要先记录一下 cur.next 不然后续的节点会丢失,即:

ListNode curNext = cur.next;  //记录cur.next

cur.next = head;  //头插

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 头插完后,新的头节点就要变成cur所指的节点,即: head = cur;

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

然后新的cur应该等于curNext 即: cur = curNext;

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

这样便完成了一次反转,我们接着套上循环就可以完成整个链表的反转。上述的代码实现:

while(cur != null) {
    ListNode curNext = cur.next;
    cur.next = head;
    head = cur;
    cur = curNext;
}

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 2)总代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) {return head;}
        if(head.next == null) {return head;}
        ListNode cur = head.next;
        head.next = null;

        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }

        return head;
    }
}

3. 链表的中间结点

题目:给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

 第一种方法:链表长度÷2 即可拿到中间节点,但是这种解法不是非常好

接下来博主讲解第二种方法:

先定义一个 fast slow

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

然后让 fast  一次走两步, slow 一次走一步

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

fast 走向空的时候,slow 就是中间位置

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

原理:有长度为n的线段,A和B在同一个起点,A的速度为B的速度的两倍,当A走到终点时,B刚好走到 n/2 处

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

上面这是个奇数的情况,在偶数条件上一样适用 

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

奇数与偶数情况唯一不一样的地方就是当代码走到最后时:

奇数情况下:   fast.next = null; 

偶数情况下:fast = null;

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

3)总代码 

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }
}

4. 链表中倒数第k个结点

题目:输入一个链表,输出该链表中倒数第k个结点。 

思路:定义一个 cur 在头节点位置,假如我们要找倒数第3个节点,那么就让cur走 length - 3 步即可到达目标位置,假如我们要找倒数第2个节点,那么就让cur走 length - 2 步即可

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 这种解法可以解决这个问题,但需要求链表的长度,这里博主想跟大家分享另一个方法:

我们首先要关注到一个问题,这个K的取值范围,如果长度为5,这里的 K <= 5  ,  K > 0

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k <= 0 || k > size()) { 
            return null;
        }
    }
}

这里把K值不合法的情况先处理掉了,可能会有人说这样也会求链表的长度啊,先别急,这里只是为了便于理解,暂时这么写,后续会删掉的

 力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

思路:跟上题一样,先定义一个 fast 和 slow ,假设我们要找倒数第二个节点,也就是说 K=2 ,我们先让fast 走 K - 1,如下图:

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

走完一步后,slow 和 fast 同时走,当 fast 走到 null 时候,slow就是我们要找的节点

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

这会不会是巧合呢?我们再来看,假设我们要找倒数第三个节点,也就是说 K = 3 ,根据上述思路让 fast 走K-1步,所以fast会先来到如下图所示位置:

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

然后让 fast 和 slow 同时走,当 fast 走到 null 时,slow就是我们要找的节点,如下图:

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

这样是不是就能解决问题了,原理是什么呢?

我们回过头来看,我们找倒数第二个节点的时候,是不是从后往前走一步即可,我们找倒数第三个节点的时候,是不是从后往前走两步,依此类推,找倒数第四个节点时候,从后往前走三步,那么当我们要找倒数第K个节点时候,是不是就是从后往前走了 K - 1 步? 而我们的 fast 最后一定会到达null这个最后的位置,相当于一条线段的终点,而我们的 slow 最终会到达我们要找的位置 K ,相当于一条线段的起点,我们回过头看上文给的思路,在一开始的时候,我们的head 和 slow 都在开始位置,如下图一

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 我们先让fast先走 K-1 步,为什么?注意这个 K - 1,他是不是 slow 与 fast 之间的距离?也就是slow 和 fast 组成的线段的长度

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

然后让slow 和 fast 同时走,是不是就相当于把这条线段往后挪?当fast这个线段的终点到达null的时候,slow这个线段的起点就刚好落在了K位置上,这整个过程类似于我们提前测量好了窗户的大小来制作玻璃(先让fast先走 K-1 步),然后把玻璃挪到窗户那里(让slow 和 fast 同时走),就可以刚刚好安上一样(刚好落在了K位置上),

过程如下图:这里以k = 2 为例子。

1.让fast走 k -1 步

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 2. 让slow 和 fast 同时走

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 当fast走到null的时候就停止,这个时候slow所处位置就是我们要找的K.

代码实现如下:

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k <= 0 || k > size()) {
            return null;
        }
        if(head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        while(count != k-1) {
            fast = fast.next;
            count++;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

我们前面说了k > size() 这个条件只是为了便于理解先这样写的,后续是会删掉的,我们现在处理这个条件,我们设置这个条件的目的是为了什么?其实就是怕K的值太大,超过我们的表长,但是我们这个方法是不是在一开始就预先算好了k值?(fast 先走 k-1 步)如果k值太大,fast还没有走到 k-1 步的时候就已经超过表长了,也就是说  fast.next == null;  所以我们可以在(fast 先走 k-1 步)这段代码处添加一个if()else()语句,如果  fast.next != null; 那就让fast继续走 k-1 步,否则返回null。

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

4)总代码   

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k <= 0) {
            return null;
        }
        if(head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        while(count != k-1) {
            if(fast.next != null) {
                fast = fast.next;
                count++;
            }else {
                return null;
            }
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

 5. 合并两个有序链表 

 题目:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

我们以下图两个链表为例。将两个链表合成一个,那么我们在结构上就要改变他,要注意这是有序链表,所以是升序的。那么头节点就应该变成headB所在的那个节点。

 力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

思路:首先,我们要申请一个虚拟节点(有些书上叫 傀儡节点),这个节点可能会有一个val值,但是这个值没有意义:

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 接着,我们就看两个链表各个节点的val值,哪个值小就往这个虚拟节点后面串:

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

串完之后,headB往后走:

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

再比较 12 和 15 谁小,是不是12小,那么我们就把0x87那个节点的next域改成值为12的节点(0x112),注意让headA往后面走,然后再比较 15 和 23 谁小,谁小就串到后面,这就是这题的思路

重复上面的过程,当我们发现有一个链表已经走到null,那么我们就不需要再比较了,因为这是个有序链表,我们直接把剩下的另一个链表直接全部串到后面即可,如下两图:

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构​ 

因为链表本身不带头节点的,我们实际返回的是0x87,也就是值为6的这个节点,那么如何返回呢?其实很简单:

return newHead.next;

 虚拟节点在这里起到标记作用

 思路总结:

1.创建虚拟节点

ListNode newHead = new ListNode(-1);

 2.比较两个链表的数 

这有个地方要注意!!我们能直接动虚拟节点的next域去指向值较小的那个节点吗?我们整个过程是不断的去串较小值的节点,这个过程会反复用到 newHead.next = xx;  如果直接改变虚拟头节点的next域,那么我们最后返回的时候会无法找到头节点,所以我们定义一个临时变量tmp,让tmp去走

ListNode tmp = newHead;

while(headA != null && headB != null){
    if(headA.val < headB.val) {
        tmp.next = headA;
        headA = headA.next;
        tmp = tmp.next;
    }else {
        tmp.next = headB;
        headB = headB.next;
        tmp = tmp.next;         
    }        
}

3. 当有一个链表为空的时候,如下图所示: 

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

if(headA != null) {  //headB为空时
    tmp.next = headA;
}

if(headB != null) {  //headA为空时
    tmp.next = headB;
}

 4. 最后返回头节点

return newHead.next;

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

 5)总代码

public class Solution {
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        ListNode newHead = new ListNode(-1);//创建虚拟节点
        ListNode tmp = newHead;

        while(headA != null && headB != null){
            if(headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }else {
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }

        if(headA != null) {
            tmp.next = headA;
        }

        if(headB != null) {
            tmp.next = headB;
        }

        return newHead.next;
    }
}

力扣链表OJ面试题,那些你不懂的全新版本解法,链表,java,数据结构

下一篇文章博主将会讲解力扣oj链表较难的题目,感兴趣的小伙伴可以去看看

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

到了这里,关于力扣链表OJ面试题,那些你不懂的全新版本解法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 顺序表、链表刷题指南(力扣OJ)

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

    2024年02月14日
    浏览(39)
  • 每日OJ题_算法_递归④力扣24. 两两交换链表中的节点

    目录 ④力扣24. 两两交换链表中的节点 解析代码 24. 两两交换链表中的节点 难度 中等 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 示例 1: 示例 2: 示例 3: 提示: 链表

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

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

    2024年02月03日
    浏览(52)
  • 人工智能中一些看不懂的代码

    def forward(self, input: Tensor, hx: Optional[Tensor] = None) - Tuple[Tensor, Tensor]: # noqa: F811         pass forward ,它的第一个参数 input 是一个 Tensor 类型的变量,第二个参数 hx 是一个可选的 Tensor 类型变量,这里使用了 Python 3.7 引入的类型注解语法。 函数返回值类型是一个由两个 Tensor 类

    2023年04月21日
    浏览(40)
  • 越来越看不懂的企业数字化转型……

    近日和一做乙方的老友相聚谈起了今年的企业数字化转型情况,都有一个整体的感受那就是: 越来越看不懂了,有价无市,看似热闹,实则观望。   经历几年疫情,行业内都普遍认为企业领导对于数字化的重视程度在提高,毕竟数字化的技术能力及所取得的成果在这两年是

    2024年02月13日
    浏览(55)
  • 连ChatGPT都不懂的五一调休,到底怎么来的?

    今天是周几? 你上了几天班了? 还要上几天班放假? 五一啥安排? 出行的票抢到了吗? 调休到底是谁发明的?! 五一劳动节是要劳动吗? 为什么昨天是周一,今天还是周一? 相信这一周的打工人,无时无刻不在发出这样的灵魂质问,毕竟有这么条热搜是#打工人的怨气可

    2024年02月01日
    浏览(48)
  • 炫云为什么要采用让人看不懂的GHZ计费?

    很多人看到炫云GHZ计费都表示看不懂,觉得麻烦,没有按核数、按线程或者按分钟计费简单易懂,甚至还被某些同行经常拿来攻击。哪为什么炫云还坚持用GHZ计费呢?哪是因为使用GHZ计费更加公平、透明,且具有硬件无关性。今天就来和大家详细说说炫云为什么要用GHZ计费。

    2024年02月05日
    浏览(62)
  • SAS硬盘和SATA硬盘傻傻分不清?不懂的看这里

    一、SAS SSD与SATA SSD的主要差异: 01 接口形态的差异 SAS(Serial Attached SCSI)即串行连接SCSI,和SATA(Serial ATA)相同,采用串行技术以获得更高的传输速度。SAS 具备2对收发通道,而SATA 仅有1对收发通道, SAS的接口技术可以向下兼容SATA,但SATA不可以反向兼容SAS接口。 SAS接口的设

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

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

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

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

    2024年02月06日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包