最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • JS算法-删除链表节点

    正文概述 掘金(一个前端王)   2021-05-01   35

    本文来自于leetcode 第 237 题 和 剑指 offer 第 18 题

    题目描述

    请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点。

    示例 1:

    输入:head = [4,5,1,9], node = 5
    输出:[4,1,9]
    解释:给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
    

    示例 2:

    输入:head = [4,5,1,9], node = 1
    输出:[4,5,9]
    解释:给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
    

    提示:

    - 链表至少包含两个节点。
    - 链表中所有节点的值都是唯一的。
    - 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
    - 不要从你的函数中返回任何结果。
    

    代码展示

    /**
     * @param {ListNode} node
     * @return {void} Do not return anything, modify node in-place instead.
     */
    var deleteNode = function(node) {
      node.val = node.next.val;
      node.next = node.next.next;
    };
    

    题目描述

    给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

    返回删除后的链表的头节点。

    示例 1:

    输入: head = [4,5,1,9], val = 5
    输出: [4,1,9]
    解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
    

    示例 2:

    输入: head = [4,5,1,9], val = 1
    输出: [4,5,9]
    解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
    

    代码展示

    方法一:单指针

    /**
     * @param {ListNode} head
     * @param {number} val
     * @return {ListNode}
     */
    var deleteNode = function(head, val) {
      let p = head;
      if (head.val === val) return head.next;
      while(p) {
        if (p.next && p.next.val === val && !p.next.next) {
          p.next = null;
          break;
        }
        if (p.val === val) {
          p.val = p.next.val;
          p.next = p.next.next;
        }
        p = p.next;
      }
      return head;
    };
    

    方法二:双指针

    /**
     * @param {ListNode} head
     * @param {number} val
     * @return {ListNode}
     */
    var deleteNode = function(head, val) {
      if (head.val === val) return head.next;
      let cur = head;
      let prev = head.next;
      while(prev) {
        if (prev && prev.val === val) {
          cur.next = prev.next;
        }
        cur = cur.next;
        prev = prev.next;
      }
      return head;
    };
    

    复杂度分析:

    时间复杂度:O(n)。

    空间复杂度:O(1)。

    总结

    双指针相比单指针性能更好,代码更为简洁明了。


    起源地 » JS算法-删除链表节点

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元