侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 154 篇文章
  • 累计创建 25 个标签
  • 累计收到 78 条评论

目 录CONTENT

文章目录

删除链表中的重复节点

神奇的程序员
2022-03-01 / 0 评论 / 1 点赞 / 146 阅读 / 3,761 字 正在检测是否收录...

前言

在一个排序的链表中,存在重复的节点,如何删除链表中重复的节点并返回删除后的链表头指针?例如:1->2->3->3->4->4->5,处理后为: 1->2->5

本文将分享这个问题的解决思路与实现代码,欢迎各位感兴趣的开发者阅读本文。

常规思路

根据题意,我们可以知道链表中的元素是排好序的。如果节点重复的话,当前节点一定与下一个节点相同。那么,我们只需要从第一个元素开始向后比对每个元素,修改节点的指针至不重复的节点,即可完成对重复节点的删除。

大体思路有了,我们来梳理下实现思路:

  • 首先,我们需要在链表的头节点之前在创建一个节点将它命名为head,用于处理第一个节点与第二节点相同的情况。

  • 其次,我们需要创建两个指针:

    • 一个指向当前不重复的节点,我们将它命名为pre
    • 一个为搜索指针,用于搜索链表中与当前节点不重复的节点,我们将它命名为last
  • 随后,我们为 prelast 进行初始赋值:

    • pre 指向head
    • last 指向head.next
  • 紧接着,我们通过while循环访问链表的每一个节点

    • last存在下一个节点且last节点的值与其下一个节点的值相等时:
      • 继续通过while循环来访问last的下一个节点,将当前节点与其下一个节点进行比对,直至找到不重复的节点
      • 找到不重复的节点后,我们修改pre的下一个节点,将其指向这个不重复的节点。
      • 修改last的指针,将其指向其下一个节点,继续向后探索。
    • 否则就继续向后探索:
      • 修改pre的指针,将其指向其节点的下一个节点
      • 修改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

示例代码

本文实例的完整代码如下:

写在最后

至此,文章就分享完毕了。

我是神奇的程序员,一位前端开发工程师。

如果你对我感兴趣,请移步我的个人网站,进一步了解。

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于神奇的程序员公众号,未经许可禁止转载💌
1

评论区