前言
在一个排序的链表中，存在重复的节点，如何删除链表中重复的节点并返回删除后的链表头指针？例如：1->2->3->3->4->4->5，处理后为: 1->2->5。
本文将分享这个问题的解决思路与实现代码，欢迎各位感兴趣的开发者阅读本文。
常规思路
根据题意，我们可以知道链表中的元素是排好序的。如果节点重复的话，当前节点一定与下一个节点相同。那么，我们只需要从第一个元素开始向后比对每个元素，修改节点的指针至不重复的节点，即可完成对重复节点的删除。
大体思路有了，我们来梳理下实现思路：
- 首先，我们需要在链表的头节点之前再创建一个节点将它命名为
head，用于处理第一个节点与第二节点相同的情况。 - 其次，我们需要创建两个指针：
- 一个指向当前不重复的节点，我们将它命名为
pre - 一个为搜索指针，用于搜索链表中与当前节点不重复的节点，我们将它命名为
last
- 随后，我们为 pre 与 last 进行初始赋值：
- pre 指向head
- last 指向head.next
- 紧接着，我们通过
while循环访问链表的每一个节点
- 修改pre的指针，将其指向其节点的下一个节点
- 修改last的指针，将其指向其节点的下一个节点
- 继续通过
while循环来访问last的下一个节点，将当前节点与其下一个节点进行比对，直至找到不重复的节点 - 找到不重复的节点后，我们修改pre的下一个节点，将其指向这个不重复的节点。
- 修改last的指针，将其指向其下一个节点，继续向后探索。
- last存在下一个节点且last节点的值与其下一个节点的值相等时：
- 否则就继续向后探索：
- 最后，我们返回head节点的下一个节点。（因为head的节点本身是我们创建的辅助节点，其下一个节点才是我们修改完后的节点）
接下来，我们通过文章开头所举的例子，将其代入上述思路，画一个图来帮助大家更好的理解上述思路，如下所示：
image-20220226224625702
实现代码
接下来，我们将上述思路转换为代码，如下所示：
/** * 删除链表中的重复节点 * @param pHead 链表头节点 */ deleteDuplicatesNode(pHead: ListNode | null): ListNode | null { if (pHead == null || pHead.next == null) return pHead; // 创建一个头节点,处理第一个与第二个节点相同的情况 const head: ListNode = { element: 0, next: pHead }; // 创建两个指针: pre指向当前不重复的节点，last为搜索指针一直向后探索寻找与当前节点不重复的节点 let pre = head; let last = head.next; while (last != null) { if (last.next != null && last.element === last.next.element) { // 向后寻找不重复的节点 while (last.next != null && last.element === last.next.element) { last = last.next; } // 将pre的指针指向不重复的节点上 pre.next = last.next; // 继续向后探索 last = last.next; } else { // 将指针指向其节点的下一个节点, 继续向后探索 pre = <ListNode>pre.next; last = last.next; } } return head.next; }
❝上述代码中的
ListNode为自定义类型，具体的代码请在本文的示例代码章节查看。
测试用例
最后，我们将开头的例子代入上述代码，验证下能否正确执行。
import { DeleteLinkedListNode } from "../DeleteLinkedListNode.ts"; import LinkedList from "../lib/LinkedList.ts"; import { printListNode } from "../utils/linked-list-models.ts"; const listNode = new LinkedList(); listNode.push(1); listNode.push(2); listNode.push(3); listNode.push(3); listNode.push(4); listNode.push(4); listNode.push(5); const pHead = deleteLinkedListNode.deleteDuplicatesNode(listNode.getHead()); // 输出修改后的链表节点 printListNode(pHead);
执行结果如下图所示：
image-20220226230022928
❝注意：printListNode用于按序输出链表中的每个节点，具体的代码请在本文的示例代码章节查看。
递归思路
接下来，我们换一种思路来解决这个问题，如果当前节点pHead与它的下一个节点相等，我们就通过新增一个指针的方式，使用while循环修改其指向，直至找到与pHead不同的节点。找到后，我们将其传入递归函数，并返回这个递归函数；如果当前节点pHead与它的下一个节点不等，我们就将其下一个节点的传入递归函数，修改pHead的下一个节点指向为此递归函数。最后，我们返回pHead节点。
我们来梳理下上述思路：
- 确定递归基线条件：
pHead或者pHead.next为null - 比对当前节点
pHead与其下一个节点pHead.next：
- 如果相等，创建一个临时指针，通过while循环继续向后探索，寻找与当前节点不重复的节点；找到后继续调用递归函数，将不重复的节点作为参数传入，最后返回这个递归函数。
- 如果不相等，则修改
pHead.next指向，使用递归函数求出当前不相等的节点，最后返回pHead。
我们将文章开头所举的例子，代入上述思路，画一下它的递归栈帮助大家更好的理解，如下所示：
image-20220228231355965
实现代码
接下来，我们将上述思路转换为代码，如下所示：
/** * 删除链表中的重复节点(递归解法) * @param pHead 链表头节点 */ deleteDuplicatesNodeForRecursion(pHead: ListNode | null): ListNode | null { // 节点不存在或只有1个节点时直接返回 if (pHead == null || pHead.next == null) return pHead; // 当前节点是重复节点 if (pHead.element === pHead.next.element) { let pNode: ListNode | null = pHead.next; // 通过遍历，找到第一个与当前节点不同的节点 while (pNode != null && pNode.element === pHead.element) { // 寻找第一个与当前节点不同的节点 pNode = pNode.next; } // 本轮递归结束，从第一个与当前节点不同的节点开始递归 return this.deleteDuplicatesNodeForRecursion(pNode); } else { // 连接不重复的节点 pHead.next = this.deleteDuplicatesNodeForRecursion(pHead.next); // 本轮轮递归结束，返回最终的链表头节点 return pHead; } }
测试用例
我们将开头的例子代入上述代码，验证下能否正确执行。
import { DeleteLinkedListNode } from "../DeleteLinkedListNode.ts"; import LinkedList from "../lib/LinkedList.ts"; import { printListNode } from "../utils/linked-list-models.ts"; listNode = new LinkedList(); listNode.push(1); listNode.push(2); listNode.push(3); listNode.push(3); listNode.push(4); listNode.push(4); listNode.push(5); const pHead = deleteLinkedListNode.deleteDuplicatesNodeForRecursion( listNode.getHead() ); // 输出修改后的链表节点 console.log("删除重复节点后，链表的剩余节点为: "); printListNode(pHead);
image-20220228233449946
示例代码
本文实例的完整代码如下：
- DeleteLinkedListNode.ts[1]
- deleteLinkedListNode-test.ts[2]
- LinkedList.ts[3]
- linked-list-models.ts[4]
写在最后
至此，文章就分享完毕了。
我是神奇的程序员，一位前端开发工程师。
如果你对我感兴趣，请移步我的个人网站[5]，进一步了解。
- 公众号无法外链，如果文中有链接，可点击下方阅读原文查看😊
