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

打印 上一主题 下一主题

主题 1764|帖子 1764|积分 5292


   
孤独的时间看世界更清楚

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

目次
1. 移除链表元素
 1)总代码
2. 反转链表
 2)总代码
3. 链表的中央结点
3)总代码 
4. 链表中倒数第k个结点
4)总代码   
 5. 合并两个有序链表 
 5)总代码


1. 移除链表元素

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

  假设我们要删除val=45的节点,那么我们起主要界说一个prev和cur,让prev指向第一个节点,cur指向第二个节点,然后我们判断cur的val是不是45?如果等于那么
   
  1. prev.next = cur.next;
复制代码
   

  这样便完成了该节点的删除,该节点就会被回收 
   
 
  接着我们便让cur今背面走一步,但是prev不能动,缘故起因是为了防止下个节点仍旧是45,当下个节点不是我们要删除的数时,就让prev向前走,使cur和prev处于同一位置(如下图1),然后再让cur今后走(如下图2)
  

  

    所以我们这里要分两种情况,一种是下个节点是我们要删除的数,另一种是下个节点不是我们要删除的数
   
  1. while(   ) {     if(cur.val == val) {    prev.next = cur.next;
  2.        cur = cur.next;    }else {        prev = cur;        cur = cur.next;}
复制代码
    当我们走到0x36这个节点,发现是45,满足我们上述代码的if条件 
  

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

    这样便把所有的45删掉了,这个时间我们return head即可,但是我们没有考虑到头节点是不是45的问题,所以我们还要完善,我先把上述过程进行代码实现:
   
  1. 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;
  2.             cur = cur.next;        }else {            prev = cur;            cur = cur.next;        }    }    //除了头节点,其他都删除完成了}
复制代码
   到了这一步,除了头节点我们都删除完了,对于头节点的处理,着实很简单:
  
   
  1. if(head.val == val) {
  2.     head = head.next;
  3. }
复制代码
   但是如果我们要在代码开始就先把头节点处理掉,这种情况的话必要加个循环,防止第一第二个节点都是我们要删除的
  

 1)总代码

  
  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;
  2.                cur = cur.next;            }else {                prev = cur;                cur = cur.next;            }            //除了头节点,其他都删除了            if(head.val == val) {                head = head.next;            }        }        return head;    }}
复制代码
2. 反转链表

题目:反转一个单链表 
    这道题要我们做的,着实就是头变尾,尾变头,终极实现下图的效果
  

   总思路:将头节点置为空 ,然后对后续的节点都进行头插,由于头插法本身就可以将链表翻转
    具体解决操作:界说cur指向当前必要翻转的节点
  

    在这里我们可以顺带处理 空表 以及 表里只有一个节点 的情况
   
  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         if(head == null) {return head;}
  4.         if(head.next == null) {return head;}
  5.         ListNode cur = head.next;
  6.         head.next = null;
  7.     }
  8. }
复制代码
   这时间 头节点 为空,我们对 cur 进行头插法,注意:在头插前要先记载一下 cur.next 不然后续的节点会丢失,即:
  ListNode curNext = cur.next;  //记载cur.next
  cur.next = head;  //头插
  

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

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

   这样便完成了一次反转,我们接着套上循环就可以完成整个链表的反转。上述的代码实现:
   
  1. while(cur != null) {
  2.     ListNode curNext = cur.next;
  3.     cur.next = head;
  4.     head = cur;
  5.     cur = curNext;
  6. }
复制代码

 2)总代码
     
  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         if(head == null) {return head;}
  4.         if(head.next == null) {return head;}
  5.         ListNode cur = head.next;
  6.         head.next = null;
  7.         while(cur != null) {
  8.             ListNode curNext = cur.next;
  9.             cur.next = head;
  10.             head = cur;
  11.             cur = curNext;
  12.         }
  13.         return head;
  14.     }
  15. }
复制代码
   3. 链表的中央结点

题目:给定一个带有头结点 head 的非空单链表,返回链表的中央结点。如果有两个中央结点,则返回第二个中央结点。
    第一种方法:链表长度÷2 即可拿到中央节点,但是这种解法不是非常好
    接下来博主解说第二种方法:
  先界说一个 fast slow
  

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

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

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

 

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

  奇数与偶数情况唯一不一样的地方就是当代码走到末了时:
  奇数情况下:   fast.next = null; 
  偶数情况下:fast = null;
  

3)总代码 

  
  1. class Solution {
  2.     public ListNode middleNode(ListNode head) {
  3.         ListNode fast = head;
  4.         ListNode slow = head;
  5.         while(fast != null && fast.next != null) {
  6.             fast = fast.next.next;
  7.             slow = slow.next;
  8.         }
  9.         return slow;
  10.     }
  11. }
复制代码
4. 链表中倒数第k个结点

题目:输入一个链表,输出该链表中倒数第k个结点。 
   思路:界说一个 cur 在头节点位置,如果我们要找倒数第3个节点,那么就让cur走 length - 3 步即可到达目标位置,如果我们要找倒数第2个节点,那么就让cur走 length - 2 步即可
  

 这种解法可以解决这个问题,但必要求链表的长度,这里博主想跟各人分享另一个方法:
   我们起主要关注到一个问题,这个K的取值范围,如果长度为5,这里的 K <= 5  ,  K > 0
   
  1. public class Solution {
  2.     public ListNode FindKthToTail(ListNode head,int k) {
  3.         if(k <= 0 || k > size()) {
  4.             return null;
  5.         }
  6.     }
  7. }
复制代码
   这里把K值不合法的情况先处理掉了,可能会有人说这样也会求链表的长度啊,先别急,这里只是为了便于明白,暂时这么写,后续会删掉的
   

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

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

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

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

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

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

   然后让slow 和 fast 同时走,是不是就相称于把这条线段今后挪?当fast这个线段的尽头到达null的时间,slow这个线段的起点就刚好落在了K位置上,这整个过程类似于我们提前丈量好了窗户的巨细来制作玻璃(先让fast先走 K-1 步),然后把玻璃挪到窗户那里(让slow 和 fast 同时走),就可以刚刚好安上一样(刚好落在了K位置上),
  过程如下图:这里以k = 2 为例子。
  1.让fast走 k -1 步

 2. 让slow 和 fast 同时走

    当fast走到null的时间就制止,这个时间slow所处位置就是我们要找的K.
  代码实现如下:
  
  1. public class Solution {
  2.     public ListNode FindKthToTail(ListNode head,int k) {
  3.         if(k <= 0 || k > size()) {
  4.             return null;
  5.         }
  6.         if(head == null) {
  7.             return null;
  8.         }
  9.         ListNode fast = head;
  10.         ListNode slow = head;
  11.         int count = 0;
  12.         while(count != k-1) {
  13.             fast = fast.next;
  14.             count++;
  15.         }
  16.         while(fast.next != null) {
  17.             fast = fast.next;
  18.             slow = slow.next;
  19.         }
  20.         return slow;
  21.     }
  22. }
复制代码
   我们前面说了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。
  

4)总代码   

  
  1. public class Solution {
  2.     public ListNode FindKthToTail(ListNode head,int k) {
  3.         if(k <= 0) {
  4.             return null;
  5.         }
  6.         if(head == null) {
  7.             return null;
  8.         }
  9.         ListNode fast = head;
  10.         ListNode slow = head;
  11.         int count = 0;
  12.         while(count != k-1) {
  13.             if(fast.next != null) {
  14.                 fast = fast.next;
  15.                 count++;
  16.             }else {
  17.                 return null;
  18.             }
  19.         }
  20.         while(fast.next != null) {
  21.             fast = fast.next;
  22.             slow = slow.next;
  23.         }
  24.         return slow;
  25.     }
  26. }
复制代码
 5. 合并两个有序链表 

 题目:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点构成的
   我们以下图两个链表为例。将两个链表合成一个,那么我们在布局上就要改变他,要注意这是有序链表,所以是升序的。那么头节点就应该酿成headB所在的谁人节点。
   

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

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

   串完之后,headB今后走:
  

   再比力 12 和 15 谁小,是不是12小,那么我们就把0x87谁人节点的next域改成值为12的节点(0x112),注意让headA今背面走,然后再比力 15 和 23 谁小,谁小就串到背面,这就是这题的思路
    重复上面的过程,当我们发现有一个链表已经走到null,那么我们就不必要再比力了,由于这是个有序链表,我们直接把剩下的另一个链表直接全部串到背面即可,如下两图:
  

​ 
   由于链表本身不带头节点的,我们实际返回的是0x87,也就是值为6的这个节点,那么如何返回呢?着实很简单:
   
  1. return newHead.next;
复制代码
    假造节点在这里起到标记作用
   思路总结:
1.创建假造节点
  
  1. ListNode newHead = new ListNode(-1);
复制代码
 2.比力两个链表的数 
   这有个地方要注意!!我们能直接动假造节点的next域去指向值较小的谁人节点吗?我们整个过程是不断的去串较小值的节点,这个过程会反复用到 newHead.next = xx;  如果直接改变假造头节点的next域,那么我们末了返回的时间会无法找到头节点,所以我们界说一个临时变量tmp,让tmp去走
  1. ListNode tmp = newHead;
  2. while(headA != null && headB != null){
  3.     if(headA.val < headB.val) {
  4.         tmp.next = headA;
  5.         headA = headA.next;
  6.         tmp = tmp.next;
  7.     }else {
  8.         tmp.next = headB;
  9.         headB = headB.next;
  10.         tmp = tmp.next;         
  11.     }        
  12. }
复制代码
3. 当有一个链表为空的时间,如下图所示: 

  1. if(headA != null) {  //headB为空时
  2.     tmp.next = headA;
  3. }
  4. if(headB != null) {  //headA为空时
  5.     tmp.next = headB;
  6. }
复制代码
 4. 末了返回头节点
  1. return newHead.next;
复制代码

 5)总代码

  1. public class Solution {
  2.     public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
  3.         ListNode newHead = new ListNode(-1);//创建虚拟节点
  4.         ListNode tmp = newHead;
  5.         while(headA != null && headB != null){
  6.             if(headA.val < headB.val) {
  7.                 tmp.next = headA;
  8.                 headA = headA.next;
  9.                 tmp = tmp.next;
  10.             }else {
  11.                 tmp.next = headB;
  12.                 headB = headB.next;
  13.                 tmp = tmp.next;
  14.             }
  15.         }
  16.         if(headA != null) {
  17.             tmp.next = headA;
  18.         }
  19.         if(headB != null) {
  20.             tmp.next = headB;
  21.         }
  22.         return newHead.next;
  23.     }
  24. }
复制代码

   下一篇文章博主将会解说力扣oj链表较难的题目,感兴趣的小伙伴可以去看看
  希望对各人有所帮助,感谢观看!!! 

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

天津储鑫盛钢材现货供应商

论坛元老
这个人很懒什么都没写!
快速回复 返回顶部 返回列表