LeetCode - 083 - 删除排序链表中的重复元素（remove-duplicates-from-sorted-list

内容简介：LeetCode - 083 - 删除排序链表中的重复元素（remove-duplicates-from-sorted-list

Create by jsliang on 2019-6-12 08:50:11
Recently revised in 2019-6-18 09:26:06

一 目录

不折腾的前端，和咸鱼有什么区别

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题代码 | | 四 执行测试 | | 五 LeetCode Submit | | 六 解题思路 | | 七 总结 |

二 前言

• 难度：简单

• 涉及知识：链表

• 题目地址：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

• 题目内容：

给定一个 排序 链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3

三 解题代码

小伙伴可以先自己在本地尝试解题，再回来看看 jsliang 的解题思路。

var deleteDuplicates = function(head) {
  if (!head) { // 预防 [] 情况
    return head;
  }
  let removal = {
    val: -99, // 预防 [-1, 1, 1, 1, 3] 情况 
    next: null,
  };
  let follower = removal;
  while (head) {
    if (head.val != follower.val) {
      follower.next = head;
      head = head.next;
      follower = follower.next;
    } else {
      if (head.next === null) { // 预防 [1, 1, 2, 3, 3] 情况
        follower.next = null;
      }
      head = head.next;
    }
  }
  return removal.next;
};

四 执行测试

• 参数： head：

let head = {
  val: 1,
  next: {
    val: 1,
    next: {
      val: 2,
      next: {
        val: 3,
        next: {
          val: 3,
          next: null
        }
      },
    }
  }
}

• 返回值： return：

{ val: 1, next: { val: 2, next: { val: 3, next: null } } }

五 LeetCode Submit

√ Accepted
  √ 165/165 cases passed (100 ms)
  √ Your runtime beats 90.76 % of javascript submissions
  √ Your memory usage beats 13.09 % of javascript submissions (36.3 MB)

六 解题思路

首先，这道题不是第一次碰到链表，小伙伴可以查看 021-合并两个有序链表（merge-two-sorted-lists），先了解一波链表的有关知识。

然后，在这道题中，我们的解题思路就可以迎刃而解了：

• 步骤 1：在代码中添加 console.log()，查看代码执行机制。

var deleteDuplicates = function(head) {
  if (!head) { // 预防 [] 情况
    return head;
  }
  let removal = {
    val: -99, // 预防 [-1, 1, 1, 1, 3] 情况 
    next: null,
  };
  let follower = removal;
  while (head) {
    console.log('------');
    console.log(head);
    console.log(removal);
    console.log(follower);
    if (head.val != follower.val) {
      follower.next = head;
      head = head.next;
      follower = follower.next;
    } else {
      if (head.next === null) { // 预防 [1, 1, 2, 3, 3] 情况
        follower.next = null;
      }
      head = head.next;
    }
  }
  return removal.next;
};
let head = { // 即 [1, 1, 2, 3, 3]
  val: 1,
  next: {
    val: 1,
    next: {
      val: 2,
      next: {
        val: 3,
        next: {
          val: 3,
          next: null
        }
      },
    }
  }
}
deleteDuplicates(head);

• 步骤 2：执行代码，得到打印信息，顺序 head -> removal -> follower。

jsliang 注释：
  第一次遍历，
  我们的 head、removal、follower 都处于初始状态
------
{ val: 1, next: { val: 1, next: { val: 2, next: { val: 3, next: { val: 3, next: null } } } } }
{ val: -99, next: null }
{ val: -99, next: null }
jsliang 注释：
  第二次遍历，
  我们的 head = head.next，follower = head.next，
  这样 removal 就获得了 1，以及之后的整个 next。
------
{ val: 1, next: { val: 2, next: { val: 3, next: { val: 3, next: null } } } }
{ val: -99, next: { val: 1, next: { val: 1, next: { val: 2, next: { val: 3, next: { val: 3, next: null } } } } } }
{ val: 1, next: { val: 1, next: { val: 2, next: { val: 3, next: { val: 3, next: null } } } } }
jsliang 注释：
  第三次遍历，
  我们的 head 继续前进一步：head = head.next，
  但是因为 head.val == follower.val，
  所以我们这次不修改 follower，从而做到去重的作用。
  （follower 的变动影响 removal 的变动）
------
{ val: 2, next: { val: 3, next: { val: 3, next: null } } }
{ val: -99, next: { val: 1, next: { val: 1, next: { val: 2, next: { val: 3, next: { val: 3, next: null } } } } } }
{ val: 1, next: { val: 1, next: { val: 2, next: { val: 3, next: { val: 3, next: null } } } } }
jsliang 注释：
  第四次遍历，
  我们的 head 继续前进一步：head = head.next，
  然后 follower 和 removal 获得了 head.next。
------
{ val: 3, next: { val: 3, next: null } }
{ val: -99, next: { val: 1, next: { val: 2, next: { val: 3, next: { val: 3, next: null } } } } }
{ val: 2, next: { val: 3, next: { val: 3, next: null } } }
jsliang 注释：
  第五次遍历，
  我们的 head 继续前进一步：head = head.next，
  此时 head.val == follower.val，
  并且 head.next == null，
  所以我们直接将 follower.next 设置为 null，
  从而获得最终结果
------
{ val: 3, next: null }
{ val: -99, next: { val: 1, next: { val: 2, next: { val: 3, next: { val: 3, next: null } } } } }
{ val: 3, next: { val: 3, next: null } }
jsliang 注释：
  最终 return 的值如下所示：
------
{ val: 1, next: { val: 2, next: { val: 3, next: null } } }

最后，小伙伴们如果还不理解，可以自行拷贝代码到本地，或者看多两遍代码，如有不懂，记得留言。

七 总结

这样，我们就搞定了 LeetCode 简单难度的第二个链表题目，想来也就那么回事，小伙伴们学会了吗~

---

不折腾的前端，和咸鱼有什么区别！

jsliang 会每天在公众号发表一篇文章，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构等等。

扫描上方二维码，关注 jsliang 的公众号，让我们一起折腾！

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

以上所述就是小编给大家介绍的《LeetCode - 083 - 删除排序链表中的重复元素（remove-duplicates-from-sorted-list》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

猜你喜欢:

• CSS 基础：块级元素、行内元素、替换元素、非替换元素
• CSS 技巧篇(六)：display设置元素为行内元素时，元素之间存在间隙问题
• 探究行内元素和块级元素
• 重学前端：块级元素与内联元素
• 使CSS伪元素：在与主元素相同的高度之前
• 求非负元素数组所有元素能组合的最大字符串

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。