• Java 算法篇-链表的经典算法：有序链表去重、合并多个有序链表

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

     

     

    文章目录

             1.0 链表的说明

             2.0 有序链表去重的实现方式

            2.1 有序链表去重(保留重复的节点) - 使用递归来实现

            2.2 有序链表去重(保留重复的节点) - 使用双指针来实现

            2.3 有序链表去重(不保留重复的节点) - 使用递归来实现

            2.4 有序链表去重(不保留重复的节点) - 使用三指针来实现

            3.0 合并升序链表

            3.1 合并升序链表(两个链表) - 迭代法

            3.2 合并升序链表(两个链表) - 递归法

            3.3 合并多个升序链表

            4.0 实现有序链表去重、合并升序链表的完整代码

            1.0 链表的说明

            为了更好的讲解本篇当中的两种经典算法，先创建一个带哨兵的链表。链表是一种常见的数据结构，用于存储一系列元素。链表由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

    代码如下：

    1. import java.util.Iterator;
    2.  
    3. public class List implements Iterable{
    4.     private  Node sentry;
    5.  
    6.     static class Node {
    7.         public int value;
    8.         public Node next;
    9.  
    10.         public Node(int value, Node next) {
    11.             this.value = value;
    12.             this.next = next;
    13.         }
    14.     }
    15.  
    16.     public List() {
    17.         sentry = new Node(-1,null);
    18.     }
    19.  
    20.     //头插节点
    21.     public void addFirst(int value) {
    22.         sentry.next = new Node(value,sentry.next);
    23.     }
    24.  
    25.     //尾插节点
    26.     public void addLast( int value) {
    27.         Node temp = sentry;
    28.         while (temp.next != null) {
    29.             temp = temp.next;
    30.         }
    31.         temp.next = new Node(value,null);
    32.     }
    33.  
    34.     //重写迭代器
    35.     @Override
    36.     public Iterator iterator() {
    37.         return new Iterator() {
    38.             Node p = sentry.next;
    39.             @Override
    40.             public boolean hasNext() {
    41.                 return p != null;
    42.             }
    43.  
    44.             @Override
    45.             public Integer next() {
    46.                 int value = p.value;
    47.                 p = p.next;
    48.                 return value;
    49.             }
    50.         };
    51.     }
    52.  
    53. }

            简单讲解一下，创建了一个链表类，该类中包含一个静态内部类，即节点类，还实现了一个基本的方法：头插节点、尾插节点、重写了迭代器等等。

    需要了解的小伙伴可以点击该链接：【Java 数据结构篇-实现单链表核心API-CSDN博客】

             2.0 有序链表去重的实现方式

            在此之前，需要分为两个方向：

            一、需要保留重复值的节点

            使用递归来实现有序链表的去重、使用双指针来实现有序链表的去重。

            二、不需要保留重复值的节点

            使用递归来实现有序链表的去重、使用三指针来实现有序链表的去重。

            2.1 有序链表去重(保留重复的节点) - 使用递归来实现

            具体思路：先来考虑终止递出的条件为：p == null 或者 p.next == null ，对于 p == null 情况，当该链表为空链表时，直接返回 null ，对于 p.next == null 情况，当递出到最后只剩一个时，也没有必要继续下去了，不会再有重复的值的节点了。再来考虑递出的具体过程：当 p.value == p.next.value 的情况，就该忽略该节点，则需要返回下一个节点；当 p.value != p.next.value 的情况，就需要返回该节点，但是在返回之前，需要对 p.next 该节点的指向进行重整。

    代码如下：

    1.     //去重方法一(保留):递归
    2.     public List removeRecursion(List list) {
    3.         Node sentry1 = list.sentry;
    4.         sentry = recursion1(sentry1);
    5.         return list;
    6.     }
    7.  
    8.     private Node recursion1(Node p) {
    9.  
    10.         if (p == null || p.next == null) {
    11.             return p;
    12.         }
    13.         if (p.value == p.next.value) {
    14.             return recursion1(p.next);
    15.         }else {
    16.             p.next = recursion1(p.next);
    17.             return p;
    18.         }
    19.  
    20.     }

            需要注意的是，先得判断链表对象是否为 null ，不然会空指针异常。

            2.2 有序链表去重(保留重复的节点) - 使用双指针来实现

            具体思路：定义两个指针 n1 与 n2 ，对于 n1 来说：n1 一开始指向头节点，假如指向哨兵节点时，那么后续就会掺入了哨兵节点的值来比较，因此，n1 一开始时需要指向头节点。对于 n2 来说，n2 = n1.next ，也就是 n2 在 n1 指向的节点的前一个节点。接下来：当 n1.value == n2.value 时，则将 n1.next = n2.next ；当 n1.value != n2.value 时，则 n1 = n1.next 。     

            循环的条件为：(n2 = n1.next) != null 。

    代码如下：

    1.     //去重方法二(保留):双指针
    2.     public List removeDoublePointer(List list) {
    3.         if (list == null) {
    4.             return null;
    5.         }
    6.  
    7.         //少于两个节点，不存在重复的值
    8.         if (list.sentry.next == null || list.sentry.next.next == null) {
    9.             return null;
    10.         }
    11.  
    12.         Node n1 = list.sentry.next;
    13.         Node n2;
    14.  
    15.         while ((n2 = n1.next) != null) {
    16.  
    17.             if (n2.value == n1.value) {
    18.                 n1.next = n2.next;
    19.             }else {
    20.                 n1 = n1.next;
    21.             }
    22.         }
    23.  
    24.         return list;
    25.     }

            需要注意的是，先得判断对象是否为 null ；还有一种情况，当节点少于两个时，不存在重复的值的节点。

            2.3 有序链表去重(不保留重复的节点) - 使用递归来实现

            具体思路：先来考虑递出的终止条件为：当 p == null 或者 p.next == null 的情况时，直接返回 p 该节点，因为当 p.next == null 时，不存在有两个重复值的节点，因此就没有必要再继续递归下去了。再来考虑递出的两种情况：当 p.value != p.next.value 时，没有重复，则返回当前节点 p ，但是在此之前，需要对 p.next 重新赋值，即重新调整 p.next 的指向；当 p.value == p.next.vaule 时，存在重复，则将该值的节点全部找出来，直到找到最后一个节点。循环的条件为： p.value == p.next.value ，循环结束后，得到的 p 就是最后一个重复值的节点，因为不需要这个节点，则返回下一个节点。

    代码如下：

    1.     //去重方法一(不保留):递归
    2.     public List removeRepeat(List list) {
    3.         Node temp = list.sentry;
    4.         sentry = recursion(temp);
    5.         return list;
    6.     }
    7.  
    8.     public Node recursion(Node p) {
    9.         if (p == null || p.next == null) {
    10.             return p;
    11.         }
    12.  
    13.         if (p.value != p.next.value) {
    14.             p.next = recursion(p.next);
    15.             return p;
    16.         }else {
    17.             while (p.value == p.next.value) {
    18.                 p = p.next;
    19.             }
    20.             return recursion(p.next);
    21.         }
    22.  
    23.     }

            同样的，也需要先判断该对象是否为 null ，否则容易报异常。

            2.4 有序链表去重(不保留重复的节点) - 使用三指针来实现

            具体思路：先定义三个指针，对于 p1 来说： 一开始时指向哨兵节点，假如不实现哨兵节点，则删除不了当链表中前几个为重复值的节点(比如：1->1->1->2->null) ，因此，需要实现哨兵来完成该需求；对与 p2 来说：一开始时指向头节点，即 p1.next；对于 p3 来说：一开始时指向头节点的下一个节点，即 p2.next 。接下来，对于循环的两种过程来分析：当 p2.value == p3.value 时，需要接着找到两个节点的值不相等的时候，所以内层循环条件为：p2.value == p3.value 且 p3 != null，这里需要特别注意的是，千万不能丢了 p3 != null 的限制条件。跳出内层循环是，就可能意味着找到了，则将 p1.next = p3 ；当 p2.value != p3.value 时，直接 p1 = p1.next 即可。外层循环的条件为：（(p2 = p1.next) != null 且 (p3 = p2.next) != null）

    代码如下：

    1.     //去重方法二(不保留):三指针
    2.     public List removeThreePointer(List list) {
    3.  
    4.         if (list == null) {
    5.             return null;
    6.         }
    7.  
    8.         Node n1 = list.sentry;
    9.         Node n2 ;
    10.         Node n3 ;
    11.         while ((n2 = n1.next) != null && (n3 = n2.next) != null) {
    12.             if (n2.value == n3.value) {
    13.                 while (n3 != null && n2.value == n3.value) {
    14.                     n3 = n3.next;
    15.                 }
    16.                 n1.next = n3;
    17.             }else {
    18.                 n1 = n1.next;
    19.             }
    20.         }
    21.         return list;
    22.     }

            这里有个小技巧，对与 p2、p3 来说，不着急赋值，在判断条件的时候再进行赋值，可以简略代码量，提高可读性。

            3.0 合并升序链表

            分为两种情况：

            一、合并两个升序链表

            使用迭代法实现合并链表、使用递归实现合并链表

            二、合并多个升序链表

            合并多个升序链表就是一个个合并两个升序链表的情况，用递归来实现

            3.1 合并升序链表(两个链表) - 迭代法

            具体思路：对于两个链表合并来说，在各自的链表中分别定义一个指针，分别指向各自的头节点。合并一条新的链表，定义一个指针指向哨兵节点。

    代码如下：

    1.     //合并升序链表
    2.     public static List combinedList(List l1,List l2) {
    3.         if (l1 == null && l2 == null) {
    4.             return null;
    5.         } else if (l1 == null) {
    6.             return l2;
    7.         } else if (l2 == null) {
    8.             return l1;
    9.         }
    10.  
    11.         List newList = new List();
    12.         Node node1 = l1.sentry.next;
    13.         Node node2 = l2.sentry.next;
    14.         Node p = newList.sentry;
    15.  
    16.         while (node1 != null && node2 != null) {
    17.  
    18.             if (node1.value < node2.value) {
    19.                 p.next = node1;
    20.                 node1 = node1.next;
    21.             }else {
    22.                 p.next = node2;
    23.                 node2 = node2.next;
    24.             }
    25.             p = p.next;
    26.         }
    27.  
    28.         if (node1 != null) {
    29.             p.next = node1;
    30.         }
    31.         if (node2 != null) {
    32.             p.next = node2;
    33.         }
    34.         return newList;
    35.     }

            

            3.2 合并升序链表(两个链表) - 递归法

            具体思路：先来考虑递出的终止条件为：当 p1 == null 时，则直接返回 p2；当 p2 == null 时，则直接返回 p1。再来考虑递出的过程：当 p1.value < p2.value 时，返回的节点为 p1 节点，在返回节点之前，需要将 p1.next 对该节点的重新调整指向下一个节点；当 p1.value >= p2.value 时，返回的节点为 p2 节点，同理，在返回该节点之前，需要将 p2.next 对该节点的重新调整指向下一个节点。

    代码如下：

    1.      private Node combineRecursion(Node p1, Node p2) {
    2.         if (p1 == null) {
    3.             return p2;
    4.         } else if (p2 == null ) {
    5.             return p1;
    6.         }
    7.  
    8.         if (p1.value < p2.value) {
    9.             p1.next = combineRecursion(p1.next,p2);
    10.             return p1;
    11.         }else {
    12.             p2.next = combineRecursion(p1,p2.next);
    13.             return p2;
    14.         }
    15.  
    16.      }

            3.3 合并多个升序链表

            具体思路：这是一个多路递归，在每一次的递归过程中，都可以看成有两个升序链表进行来合并。

    代码如下：

    1.      //实现多个升序链表合并
    2.     public List moreCombine(Node[] nodes) {
    3.         List list = new List();
    4.         list.sentry.next = moreCombineRecursion(nodes,0, nodes.length-1);
    5.         return list;
    6.     }
    7.  
    8.     private Node moreCombineRecursion(Node[] nodes,int i,int j) {
    9.  
    10.         if (j == 1) {
    11.             return nodes[i];
    12.         }
    13.         int mid = (i + j) >>> 1;
    14.         Node left = moreCombineRecursion(nodes,i,mid);
    15.         Node right = moreCombineRecursion(nodes,mid+1,j);
    16.         return combineRecursion(left,right);
    17.     }

    举例画图分析：

            对以上的流程图简单分析：注意的是结束递出的条件为：i == j 结束递出，开始回归。回归的是每一个链表的节点，最后集齐了两个链表，需要通过利用两个链表升序合并的返回进行合并，可以用迭代法或者递归法。这只是其中的一小部分，不过每一个过程都是一样的，就不多赘述了。

     

            4.0 实现有序链表去重、合并升序链表的完整代码

     

    1. import java.util.Iterator;
    2.  
    3. public class List implements Iterable{
    4.     private  Node sentry;
    5.  
    6.     static class Node {
    7.         public int value;
    8.         public Node next;
    9.  
    10.         public Node(int value, Node next) {
    11.             this.value = value;
    12.             this.next = next;
    13.         }
    14.     }
    15.  
    16.     public List() {
    17.         sentry = new Node(-1,null);
    18.     }
    19.  
    20.     //头插节点
    21.     public void addFirst(int value) {
    22.         sentry.next = new Node(value,sentry.next);
    23.     }
    24.  
    25.     //尾插节点
    26.     public void addLast( int value) {
    27.         Node temp = sentry;
    28.         while (temp.next != null) {
    29.             temp = temp.next;
    30.         }
    31.         temp.next = new Node(value,null);
    32.     }
    33.  
    34.     //重写迭代器
    35.     @Override
    36.     public Iterator iterator() {
    37.         return new Iterator() {
    38.             Node p = sentry.next;
    39.             @Override
    40.             public boolean hasNext() {
    41.                 return p != null;
    42.             }
    43.  
    44.             @Override
    45.             public Integer next() {
    46.                 int value = p.value;
    47.                 p = p.next;
    48.                 return value;
    49.             }
    50.         };
    51.     }
    52.  
    53.     //去重方法二(保留):双指针
    54.     public List removeDoublePointer(List list) {
    55.         if (list == null) {
    56.             return null;
    57.         }
    58.  
    59.         //少于两个节点，不存在重复的值
    60.         if (list.sentry.next == null || list.sentry.next.next == null) {
    61.             return null;
    62.         }
    63.  
    64.         Node n1 = list.sentry.next;
    65.         Node n2;
    66.  
    67.         while ((n2 = n1.next) != null) {
    68.  
    69.             if (n2.value == n1.value) {
    70.                 n1.next = n2.next;
    71.             }else {
    72.                 n1 = n1.next;
    73.             }
    74.         }
    75.  
    76.         return list;
    77.     }
    78.  
    79.  
    80.     //去重方法一(保留):递归
    81.     public List removeRecursion(List list) {
    82.         Node sentry1 = list.sentry;
    83.         sentry = recursion1(sentry1);
    84.         return list;
    85.     }
    86.  
    87.     private Node recursion1(Node p) {
    88.  
    89.         if (p == null || p.next == null) {
    90.             return p;
    91.         }
    92.         if (p.value == p.next.value) {
    93.             return recursion1(p.next);
    94.         }else {
    95.             p.next = recursion1(p.next);
    96.             return p;
    97.         }
    98.  
    99.     }
    100.  
    101.  
    102.  
    103.     //去重方法一(不保留):递归
    104.     public List removeRepeat(List list) {
    105.         Node temp = list.sentry;
    106.         sentry = recursion(temp);
    107.         return list;
    108.     }
    109.  
    110.     public Node recursion(Node p) {
    111.         if (p == null || p.next == null) {
    112.             return p;
    113.         }
    114.  
    115.         if (p.value != p.next.value) {
    116.             p.next = recursion(p.next);
    117.             return p;
    118.         }else {
    119.             while (p.value == p.next.value) {
    120.                 p = p.next;
    121.             }
    122.             return recursion(p.next);
    123.         }
    124.  
    125.     }
    126.  
    127.  
    128.     //去重方法二(不保留):三指针
    129.     public List removeThreePointer(List list) {
    130.  
    131.         if (list == null) {
    132.             return null;
    133.         }
    134.  
    135.         Node n1 = list.sentry;
    136.         Node n2 ;
    137.         Node n3 ;
    138.         while ((n2 = n1.next) != null && (n3 = n2.next) != null) {
    139.             if (n2.value == n3.value) {
    140.                 while (n3 != null && n2.value == n3.value) {
    141.                     n3 = n3.next;
    142.                 }
    143.                 n1.next = n3;
    144.             }else {
    145.                 n1 = n1.next;
    146.             }
    147.         }
    148.         return list;
    149.     }
    150.  
    151.  
    152.     //合并升序链表
    153.     public static List combinedList(List l1,List l2) {
    154.         if (l1 == null && l2 == null) {
    155.             return null;
    156.         } else if (l1 == null) {
    157.             return l2;
    158.         } else if (l2 == null) {
    159.             return l1;
    160.         }
    161.  
    162.         List newList = new List();
    163.         Node node1 = l1.sentry.next;
    164.         Node node2 = l2.sentry.next;
    165.         Node p = newList.sentry;
    166.  
    167.         while (node1 != null && node2 != null) {
    168.  
    169.             if (node1.value < node2.value) {
    170.                 p.next = node1;
    171.                 node1 = node1.next;
    172.             }else {
    173.                 p.next = node2;
    174.                 node2 = node2.next;
    175.             }
    176.             p = p.next;
    177.         }
    178.  
    179.         if (node1 != null) {
    180.             p.next = node1;
    181.         }
    182.         if (node2 != null) {
    183.             p.next = node2;
    184.         }
    185.         return newList;
    186.     }
    187.  
    188.     //合并链表:递归实现
    189.     public List combineList(List list2) {
    190.         List newList = new List();
    191.         Node p1 = this.sentry.next;
    192.         Node p2 = list2.sentry.next;
    193.         Node p = combineRecursion(p1,p2);
    194.         newList.sentry.next = p;
    195.         return newList;
    196.     }
    197.  
    198.      private Node combineRecursion(Node p1, Node p2) {
    199.         if (p1 == null) {
    200.             return p2;
    201.         } else if (p2 == null ) {
    202.             return p1;
    203.         }
    204.  
    205.         if (p1.value < p2.value) {
    206.             p1.next = combineRecursion(p1.next,p2);
    207.             return p1;
    208.         }else {
    209.             p2.next = combineRecursion(p1,p2.next);
    210.             return p2;
    211.         }
    212.  
    213.      }
    214.  
    215.      //实现多个升序链表合并
    216.     public List moreCombine(Node[] nodes) {
    217.         List list = new List();
    218.         list.sentry.next = moreCombineRecursion(nodes,0, nodes.length-1);
    219.         return list;
    220.     }
    221.  
    222.     private Node moreCombineRecursion(Node[] nodes,int i,int j) {
    223.  
    224.         if (j == i) {
    225.             return nodes[i];
    226.         }
    227.         int mid = (i + j) >>> 1;
    228.         Node left = moreCombineRecursion(nodes,i,mid);
    229.         Node right = moreCombineRecursion(nodes,mid+1,j);
    230.         return combineRecursion(left,right);
    231.     }
    232.  
    233. }

             

  • 相关阅读:
    VT 入门番外篇——最小 VT 实现（上）
    介绍一款 SaaS 服务器监控工具： CloudStats
    软件的开发模型
    c++ lambda 表达式
    2022年全球及中国工程机械租赁行业头部企业市场占有率及排名调研报告
    Mysql查询去空格方法汇总
    电梯的测试用例
    开发yocto系统-1
    源码编译安装部署lnmp
    mysql中DQL查询语句的使用级联操作
  • 原文地址：https://blog.csdn.net/Tingfeng__/article/details/134470372