• Java 算法篇-链表的经典算法：根据值删除节点、删除倒数第 n 个节点

    🔥博客主页： 小扳_-CSDN博客
    ❤感谢大家点赞👍收藏⭐评论✍      

     

     

     

    文章目录

            1.0 链表的创建

            2.0 链表的经典算法 - 根据值来删除节点

            2.1 根据值来删除节点 - 遍历链表来实现

            2.2 根据值来删除节点 - 递归实现

            3.0 链表的经典算法 - 删除倒数第 n 个节点

            3.1 删除倒数第 n 个节点 - 使用递归来实现

            3.2 删除倒数第 n 个节点 - 快慢指针来实现

            4.0 本篇链表的经典算法的完整实现代码

            1.0 链表的创建

            为了更好的讲解算法的具体内容，先创建好链表，实现一个带哨兵的单链表。

    代码如下：

    1. import java.util.Iterator;
    2.  
    3. public class List implements Iterable{
    4.     private  Node hand;
    5.  
    6.     static class Node {
    7.         public int value;
    8.         public Node next;
    9.  
    10.         public Node() {
    11.         }
    12.  
    13.         public Node(int value, Node next) {
    14.             this.value = value;
    15.             this.next = next;
    16.         }
    17.  
    18.     }
    19.  
    20.     public List() {
    21.         hand = new Node(0,null);
    22.     }
    23.  
    24.     @Override
    25.     public Iterator iterator() {
    26.         return new Iterator() {
    27.             Node p = hand.next;
    28.             @Override
    29.             public boolean hasNext() {
    30.                 return p != null;
    31.             }
    32.  
    33.             @Override
    34.             public Integer next() {
    35.                 int value = p.value;
    36.                 p = p.next;
    37.                 return value;
    38.             }
    39.         };
    40.     }
    41.  
    42.  
    43. }

            之前的篇章都有讲解过以上的每一个方法及其作用，需要了解的点击一下链接：

    Java 算法篇-深入了解单链表的反转（实现：用 5 种方式来具体实现）-CSDN博客

            2.0 链表的经典算法 - 根据值来删除节点

            介绍两种方式来实现该算法：

            一、遍历链表来实现

            二、使用递归来实现

            2.1 根据值来删除节点 - 遍历链表来实现

            实现思路为：设置两个节点分别为： o1， 一开始指向哨兵节点。o2，一开始指向头节点（也就是 哨兵节点指向的节点），想让 o2 节点往后走一步，来判断当前 o2 的节点的值是否为需要的节点，若是，则让 o1 指向 o2.next 节点，然后 o2 = o1.next  接着往后走；若不是，则让 o1 = o2 完成赋值（意味着 o1 永远跟着 o2 节点后面，o2 永远比 o1 走前一步），接着 o2 = o2.next 往后走。循环终止的条件为，当 o2 == null 就该停止了。

    代码如下：

    1.     //根据值来删除节点
    2.     public void removeValue( List list, int value) {
    3.         Node o1 = list.hand;
    4.         Node o2 = list.hand.next;
    5.         while (o2 != null) {
    6.  
    7.             if (o2.value == value) {
    8.                 o1.next = o2.next;
    9.                 o2 = o1.next;
    10.             }else {
    11.                 o1 = o2;
    12.                 o2 = o2.next;
    13.             }
    14.         }
    15.  
    16.     }

            再讲个好理解的思路：把 o1 比作战场上的大部队，把 o2 比作地雷兵，每一次往前走的时候，都需要让地雷兵先去排雷，若前方没雷时，这时候 o1 紧跟着 o2 走过的路径；若前方发现雷时，需要排除掉，以此类推，直到走完。

            2.2 根据值来删除节点 - 递归实现

            实现的思路：先把需要删除节点的链表进行递归到底进行展示出来，也就是一直递归到底，然后在回归的时候，当 p == null 说明了已经到了链表的底部了，直接返回 null 就好了。需要来判断该节点的值是否需要删除：若不需要删除的节点，在回归的时候需要返回自己的节点，然后需要更新该节点的指向。若需要删除的节点，在回归的时候直接返回 下一个节点。

    代码如下：

    1.     private Node recursion1(Node p, int value) {
    2.  
    3.         if (p == null) {
    4.             return null;
    5.         }
    6.         if (p.value == value) {
    7.             return recursion1(p.next, value);
    8.         }else {
    9.             p.next = recursion1(p.next, value);
    10.             return p;
    11.         }
    12.     }

    结合代码来具体的实现流程：

            

            3.0 链表的经典算法 - 删除倒数第 n 个节点

            介绍两种方式来实现该算法：

            一、使用递归来实现

            二、使用快慢指针来实现

            3.1 删除倒数第 n 个节点 - 使用递归来实现

            实现思路：先递出到底 p == null 返回 0 ，接着然后每一次回归都对当前的 i 进行 i++，再来判断是否 i == n，但是我们细想一下，我们得到了 i == n 这个要删除的节点是不是没有什么用，因此，我们实际需要找的节点是 n + 1，当 i == n + 1 时，就可以删除倒数第 n 个节点了 p.next = p.next.next 这样就删除了节点了。

    代码如下：

    1.     //删除倒数第 n 个节点(递归法)
    2.     public List deleteCount(List list, int n) {
    3.         recursion(list.hand,n);
    4.         return list;
    5.     }
    6.  
    7.     private int  recursion(Node p, int n) {
    8.  
    9.         if (p == null) {
    10.             return 0;
    11.         }
    12.         int i = recursion(p.next, n);
    13.         i++;
    14.         if (i == n + 1) {
    15.             p.next = p.next.next;
    16.         }
    17.  
    18.         return i;
    19.     }

            需要注意的是，这里一定要用带上哨兵的链表，原因是：当我要删除的节点是第一个的时候，没哨兵是完成不了这个操作的。

            3.2 删除倒数第 n 个节点 - 快慢指针来实现

            思路：先定义两个 fast、slow 快慢指针，一开的时候都指向哨兵节点，然后让 slow 先跑 n+1个节点，然后就两个指针 一起跑，循环的结束条件为： slow == null ，因为当 slow == null是，fast.next 刚好指向了要删除的节点，那么直接就用 fast.next = fast.next.next 这就把第 n 个节点删除掉了。

    代码如下：

    1.     //删除倒数第n个节点(快慢指针)
    2.  
    3.     public List removeFastSlowPointers(List list, int n) {
    4.         list.hand = fastSlowPointers(list.hand,n);
    5.         return list;
    6.     }
    7.  
    8.     private Node fastSlowPointers(Node hand, int n) {
    9.         Node temp = hand;
    10.         Node fast = hand;
    11.         Node slow = hand;
    12.         for (int i = 0; i < n + 1; i++) {
    13.             slow = slow.next;
    14.         }
    15.         while (slow != null) {
    16.             slow = slow.next;
    17.             fast = fast.next;
    18.         }
    19.         fast.next = fast.next.next;
    20.         return temp;
    21.     }

            这里需要注意的是，当要删除第 1 个节点的时候，若没有哨兵节点的时候，是完成不了这个操作的。还有需要注意的是，关于要删除第 n 个节点，实际要找到第 n+1 个节点才能对第 n 个节点进行删除。

            4.0 本篇链表的经典算法的完整实现代码

    1. import java.util.Iterator;
    2.  
    3. public class List implements Iterable{
    4.     private  Node hand;
    5.  
    6.     static class Node {
    7.         public int value;
    8.         public Node next;
    9.  
    10.         public Node() {
    11.         }
    12.  
    13.         public Node(int value, Node next) {
    14.             this.value = value;
    15.             this.next = next;
    16.         }
    17.  
    18.     }
    19.  
    20.     public List() {
    21.         hand = new Node(0,null);
    22.     }
    23.  
    24.     @Override
    25.     public Iterator iterator() {
    26.         return new Iterator() {
    27.             Node p = hand.next;
    28.             @Override
    29.             public boolean hasNext() {
    30.                 return p != null;
    31.             }
    32.  
    33.             @Override
    34.             public Integer next() {
    35.                 int value = p.value;
    36.                 p = p.next;
    37.                 return value;
    38.             }
    39.         };
    40.     }
    41.  
    42.  
    43.     //头插节点
    44.     public void addFirst(int value) {
    45.         hand.next = new Node(value,hand.next);
    46.     }
    47.  
    48.     //尾插节点
    49.     public void addLst(int value) {
    50.         Node p = hand;
    51.         while (p.next != null) {
    52.             p = p.next;
    53.         }
    54.         p.next = new Node(value,null);
    55.     }
    56.  
    57.  
    58.     //根据值来删除节点
    59.     public void removeValue( List list, int value) {
    60.         Node o1 = list.hand;
    61.         Node o2 = list.hand.next;
    62.         while (o2 != null) {
    63.  
    64.             if (o2.value == value) {
    65.                 o1.next = o2.next;
    66.                 o2 = o1.next;
    67.             }else {
    68.                 o1 = o2;
    69.                 o2 = o2.next;
    70.             }
    71.         }
    72.  
    73.     }
    74.  
    75.     //根据值来删除节点(递归实现)
    76.     public List removeRecursion(List list ,int value) {
    77.         Node p = list.hand.next;
    78.         Node tp = recursion1(p,value);
    79.         list.hand.next = tp;
    80.         return list;
    81.     }
    82.  
    83.     private Node recursion1(Node p, int value) {
    84.  
    85.         if (p == null) {
    86.             return null;
    87.         }
    88.         if (p.value == value) {
    89.             return recursion1(p.next, value);
    90.         }else {
    91.             p.next = recursion1(p.next, value);
    92.             return p;
    93.         }
    94.     }
    95.  
    96.  
    97.     //删除倒数第n个节点(递归法)
    98.     public List deleteCount(List list, int n) {
    99.         recursion(list.hand,n);
    100.         return list;
    101.     }
    102.  
    103.     private int  recursion(Node p, int n) {
    104.  
    105.         if (p == null) {
    106.             return 0;
    107.         }
    108.         int i = recursion(p.next, n);
    109.         i++;
    110.         if (i == n + 1) {
    111.             p.next = p.next.next;
    112.         }
    113.  
    114.         return i;
    115.     }
    116.  
    117.  
    118.     //删除倒数第n个节点(快慢指针)
    119.  
    120.     public List removeFastSlowPointers(List list, int n) {
    121.         list.hand = fastSlowPointers(list.hand,n);
    122.         return list;
    123.     }
    124.  
    125.     private Node fastSlowPointers(Node hand, int n) {
    126.         Node temp = hand;
    127.         Node fast = hand;
    128.         Node slow = hand;
    129.         for (int i = 0; i < n + 1; i++) {
    130.             slow = slow.next;
    131.         }
    132.         while (slow != null) {
    133.             slow = slow.next;
    134.             fast = fast.next;
    135.         }
    136.         fast.next = fast.next.next;
    137.         return temp;
    138.     }
    139.     
    140. }

  • 相关阅读:
    航迹管理软件——SPx Track Manager
    可以从以下几点着手选择期货开户公司
    Servlet1和postman的使用
    解决在选项卡中，只有默认选项里的vue-seamless-scroll可以滚动的问题
    认识matlab
    STM32G070RBT6-MCU温度测量（ADC）
    Stm32_点灯
    单例模式详解
    在cesuim上展示二维模型
    Linux三剑客命令---grep
  • 原文地址：https://blog.csdn.net/Tingfeng__/article/details/134415598