203 - 移除链表元素(remove-linked-list-elements)

Create by jsliang on 2019-07-09 19:01:37
Recently revised in 2019-07-09 19:52:55

一 目录

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

目录
一 目录
二 前言
三 解题
3.1 解法 - 正常解法
3.2 解法 - 递归

二 前言

返回目录

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

三 解题

返回目录

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

3.1 解法 - 正常解法

返回目录

  • 解题代码
var removeElements = function(head, val) {
  let result = {
    val: -99,
    next: head,
  };
  let chase = result;
  while(chase.next) {
    if (chase.next.val === val) {
      chase.next = chase.next.next;
    } else {
      chase = chase.next;
    }
  }
  return result.next;
};
  • 执行测试

head

let head = {
  val: 1, next: {
    val: 2, next: {
      val: 6, next: {
        val: 3, next: {
          val: 4, next: {
            val: 5, next: {
              val: 6, next: null,
            },
          },
        },
      },
    },
  },
};

return

let head = {
  val: 1, next: {
    val: 2, next: {
      val: 3, next: {
        val: 4, next: {
          val: 5, next: null
        },
      },
    },
  },
};
  • LeetCode Submit
✔ Accepted
  ✔ 65/65 cases passed (104 ms)
  ✔ Your runtime beats 90.76 % of javascript submissions
  ✔ Your memory usage beats 24.79 % of javascript submissions (37.5 MB)
  • 解题思路

虽然链表做过几次,但是感觉印象不深。

在前面的 LeetCode 题目中,我们做过几次链表,但是因为过久没接触,感觉又有些淡忘了,现在刚好重新复习。

首先,我们需要了解下链表的结构:

let head = {
  val: 1, next: {
    val: 2, next: {
      val: 6, next: {
        val: 3, next: {
          val: 4, next: {
            val: 5, next: {
              val: 6, next: null,
            },
          },
        },
      },
    },
  },
};

小伙伴们可以发现,相对于 来说,链表 比较简单一点,一个 val 显示当前的值,一个 next 指向下一个节点。

然后,我们要如何将其中的 6 节点去掉呢?

var removeElements = function(head, val) {
  let result = {
    val: -99,
    next: head,
  };
  let chase = result;
  while(chase.next) {
    if (chase.next.val === val) {
      chase.next = chase.next.next;
    } else {
      chase = chase.next;
    }
  }
  return result.next;
};
  1. 新建一个 result 节点,用来获取最终的节点。因为我们不能直接引用 head(非址引用),所以我们创造一个,最后只需要指向它的 next,即可返回正确的链表。
  2. 新建一个 chase 追逐者节点,用来追逐 head 的推进。
  3. 我们在循环中判断,这个追逐节点的下一个节点的值,是否是需要去掉的值。如果是,我们则指向下下一层;如果不是,我们则指向下一层。
  4. 直到 chase 没有下一层(即 nextnull)后,我们返回最终结果。

最后,完成了本题的题解。

3.2 解法 - 递归

返回目录

  • 解题代码
var removeElements = function(head, val) {
  if (!head) {
    return null;
  }
  head.next = removeElements(head.next, val);
  if (head.val === val) {
    return head.next;
  } else {
    return head;
  }
};
  • 执行测试
✔ Accepted
  ✔ 65/65 cases passed (104 ms)
  ✔ Your runtime beats 90.76 % of javascript submissions
  ✔ Your memory usage beats 24.79 % of javascript submissions (37.5 MB)
  • LeetCode Submit
✔ Accepted
  ✔ 65/65 cases passed (120 ms)
  ✔ Your runtime beats 66.03 % of javascript submissions
  ✔ Your memory usage beats 5.13 % of javascript submissions (38.2 MB)
  • 解题思路

光明正大的偷懒。


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

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

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

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

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-09 19:52:55

results matching ""

    No results matching ""