博客主页：【小扳_-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 链表的说明

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

代码如下：

import java.util.Iterator;public class List implements Iterable{privateNode sentry;static class Node {public int value;public Node next;public Node(int value, Node next) {this.value = value;this.next = next;}}public List() {sentry = new Node(-1,null);}//头插节点public void addFirst(int value) {sentry.next = new Node(value,sentry.next);}//尾插节点public void addLast( int value) {Node temp = sentry;while (temp.next != null) {temp = temp.next;}temp.next = new Node(value,null);}//重写迭代器@Overridepublic Iterator iterator() {return new Iterator() {Node p = sentry.next;@Overridepublic boolean hasNext() {return p != null;}@Overridepublic Integer next() {int value = p.value;p = p.next;return value;}};}}

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

需要了解的小伙伴可以点击该链接：【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 该节点的指向进行重整。

代码如下：

//去重方法一(保留):递归public List removeRecursion(List list) {Node sentry1 = list.sentry;sentry = recursion1(sentry1);return list;}private Node recursion1(Node p) {if (p == null || p.next == null) {return p;}if (p.value == p.next.value) {return recursion1(p.next);}else {p.next = recursion1(p.next);return p;}}

需要注意的是，先得判断链表对象是否为 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 。

代码如下：

//去重方法二(保留):双指针public List removeDoublePointer(List list) {if (list == null) {return null;}//少于两个节点，不存在重复的值if (list.sentry.next == null || list.sentry.next.next == null) {return null;}Node n1 = list.sentry.next;Node n2;while ((n2 = n1.next) != null) {if (n2.value == n1.value) {n1.next = n2.next;}else {n1 = n1.next;}}return list;}

需要注意的是，先得判断对象是否为 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 就是最后一个重复值的节点，因为不需要这个节点，则返回下一个节点。

代码如下：

//去重方法一(不保留):递归public List removeRepeat(List list) {Node temp = list.sentry;sentry = recursion(temp);return list;}public Node recursion(Node p) {if (p == null || p.next == null) {return p;}if (p.value != p.next.value) {p.next = recursion(p.next);return p;}else {while (p.value == p.next.value) {p = p.next;}return recursion(p.next);}}

同样的，也需要先判断该对象是否为 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）

代码如下：

//去重方法二(不保留):三指针public List removeThreePointer(List list) {if (list == null) {return null;}Node n1 = list.sentry;Node n2 ;Node n3 ;while ((n2 = n1.next) != null && (n3 = n2.next) != null) {if (n2.value == n3.value) {while (n3 != null && n2.value == n3.value) {n3 = n3.next;}n1.next = n3;}else {n1 = n1.next;}}return list;}

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

3.0 合并升序链表

分为两种情况：

一、合并两个升序链表

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

二、合并多个升序链表

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

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

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

代码如下：

//合并升序链表public static List combinedList(List l1,List l2) {if (l1 == null && l2 == null) {return null;} else if (l1 == null) {return l2;} else if (l2 == null) {return l1;}List newList = new List();Node node1 = l1.sentry.next;Node node2 = l2.sentry.next;Node p = newList.sentry;while (node1 != null && node2 != null) {if (node1.value < node2.value) {p.next = node1;node1 = node1.next;}else {p.next = node2;node2 = node2.next;}p = p.next;}if (node1 != null) {p.next = node1;}if (node2 != null) {p.next = node2;}return newList;}

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

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

代码如下：

 private Node combineRecursion(Node p1, Node p2) {if (p1 == null) {return p2;} else if (p2 == null ) {return p1;}if (p1.value < p2.value) {p1.next = combineRecursion(p1.next,p2);return p1;}else {p2.next = combineRecursion(p1,p2.next);return p2;} }

3.3 合并多个升序链表

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

代码如下：

 //实现多个升序链表合并public List moreCombine(Node[] nodes) {List list = new List();list.sentry.next = moreCombineRecursion(nodes,0, nodes.length-1);return list;}private Node moreCombineRecursion(Node[] nodes,int i,int j) {if (j == 1) {return nodes[i];}int mid = (i + j) >>> 1;Node left = moreCombineRecursion(nodes,i,mid);Node right = moreCombineRecursion(nodes,mid+1,j);return combineRecursion(left,right);}

举例画图分析：

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

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

import java.util.Iterator;public class List implements Iterable{privateNode sentry;static class Node {public int value;public Node next;public Node(int value, Node next) {this.value = value;this.next = next;}}public List() {sentry = new Node(-1,null);}//头插节点public void addFirst(int value) {sentry.next = new Node(value,sentry.next);}//尾插节点public void addLast( int value) {Node temp = sentry;while (temp.next != null) {temp = temp.next;}temp.next = new Node(value,null);}//重写迭代器@Overridepublic Iterator iterator() {return new Iterator() {Node p = sentry.next;@Overridepublic boolean hasNext() {return p != null;}@Overridepublic Integer next() {int value = p.value;p = p.next;return value;}};}//去重方法二(保留):双指针public List removeDoublePointer(List list) {if (list == null) {return null;}//少于两个节点，不存在重复的值if (list.sentry.next == null || list.sentry.next.next == null) {return null;}Node n1 = list.sentry.next;Node n2;while ((n2 = n1.next) != null) {if (n2.value == n1.value) {n1.next = n2.next;}else {n1 = n1.next;}}return list;}//去重方法一(保留):递归public List removeRecursion(List list) {Node sentry1 = list.sentry;sentry = recursion1(sentry1);return list;}private Node recursion1(Node p) {if (p == null || p.next == null) {return p;}if (p.value == p.next.value) {return recursion1(p.next);}else {p.next = recursion1(p.next);return p;}}//去重方法一(不保留):递归public List removeRepeat(List list) {Node temp = list.sentry;sentry = recursion(temp);return list;}public Node recursion(Node p) {if (p == null || p.next == null) {return p;}if (p.value != p.next.value) {p.next = recursion(p.next);return p;}else {while (p.value == p.next.value) {p = p.next;}return recursion(p.next);}}//去重方法二(不保留):三指针public List removeThreePointer(List list) {if (list == null) {return null;}Node n1 = list.sentry;Node n2 ;Node n3 ;while ((n2 = n1.next) != null && (n3 = n2.next) != null) {if (n2.value == n3.value) {while (n3 != null && n2.value == n3.value) {n3 = n3.next;}n1.next = n3;}else {n1 = n1.next;}}return list;}//合并升序链表public static List combinedList(List l1,List l2) {if (l1 == null && l2 == null) {return null;} else if (l1 == null) {return l2;} else if (l2 == null) {return l1;}List newList = new List();Node node1 = l1.sentry.next;Node node2 = l2.sentry.next;Node p = newList.sentry;while (node1 != null && node2 != null) {if (node1.value < node2.value) {p.next = node1;node1 = node1.next;}else {p.next = node2;node2 = node2.next;}p = p.next;}if (node1 != null) {p.next = node1;}if (node2 != null) {p.next = node2;}return newList;}//合并链表:递归实现public List combineList(List list2) {List newList = new List();Node p1 = this.sentry.next;Node p2 = list2.sentry.next;Node p = combineRecursion(p1,p2);newList.sentry.next = p;return newList;} private Node combineRecursion(Node p1, Node p2) {if (p1 == null) {return p2;} else if (p2 == null ) {return p1;}if (p1.value >> 1;Node left = moreCombineRecursion(nodes,i,mid);Node right = moreCombineRecursion(nodes,mid+1,j);return combineRecursion(left,right);}}