第1.7篇·删除排序链表中的重复元素

算法是求职的敲门砖，大厂面试一面几乎都会问算法题，以此来考察候选人的思维逻辑及编码能力。

今天要AC的题目叫做「删除排序链表中的重复元素」，在 leetcode 上的原题链接为：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

1. 题目

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表。

示例 1：

输入：head = [1,1,2] 输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3] 输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序排列

链表数据结构如下：

public class ListNode {
  int val;
  ListNode next;
  ListNode() {
  }
  ListNode(int val) {
    this.val = val;
  }
  ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
  }
}

2. 解题思路

首先理解一下题意，给出一个按照升序排序的链表，这里需要注意的是，这个链表是升序的。要求输出删除所有重复的元素。

既然链表是有顺序的，那么重复的元素必然是相邻的，我们只需要遍历一次链表，将当前节点后值相同的节点删除即可，最后得到的就是一个不重复的链表。

那么问题就来到了——如何删除一个链表中的节点？

这也很容易实现，我们知道链表的节点有两个属性——val 和 next，val 代表了当前节点的数值，next 代码了下一个节点的引用，如果我们想删除当前节点的下一个节点，只需要做以下改动：

node.next = node.next.next

即将当前节点的 next 属性指向当前节点的下一个节点的下一个节点即可。

我们用图来描述此操作就是：

当然这里还有可以优化的地方，那就是第三个节点的 next 指针依然指向第四个节点，我们可以将第三个节点的 next 指针赋值为 null，这样做是为了帮助垃圾回收器进行垃圾回收。

用 Java 实现上述思路的代码是：

上述示例代码在 leetcode 上的执行结果是：

最后，本文收录于个人语雀知识库: 我所理解的后端技术，欢迎来访。