精华内容
下载资源
问答
  • JS删除链表的节点

    2020-05-16 12:27:35
    给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。 返回删除后的链表的头节点。 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点,那么在调用...

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

    示例 1:
    输入: head = [4,5,1,9], val = 5
    输出: [4,1,9]
    解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
    
    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    /**
     * @param {ListNode} head
     * @param {number} val
     * @return {ListNode}
     */
    var deleteNode = function(head, val) {
        if(!head) return;
        if(head.val == val){
            return head.next;
        }   
        if(head.next.val == val){
                 head.next = head.next.next;
        }else{
             deleteNode(head.next,val);
        }return head;
    };
    
    展开全文
  • 删除链表中重复的结点 相似题目: leetcode-java 删除排序链表中的重复元素–保留一个元素 leetcode-java 删除排序链表中的重复元素II – 不保留重复元素 上面用的方法会多一点,可以从多个角度理解一下 题目描述:...

    删除链表中重复的结点

    相似题目:
    leetcode-java 删除排序链表中的重复元素–保留一个元素
    leetcode-java 删除排序链表中的重复元素II – 不保留重复元素

    上面用的方法会多一点,可以从多个角度理解一下
    

    题目描述:

    	在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 
    	例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
    

    问题分析:

    	方法一:
    		直接修改
    		不保留重复元素,注意设置一个新的头结点
    	
    方法二:
    	遍历放在数组中,去重,链接
    	放在数组中的方式还有点问题,对于后面的链接还有点问题
    

    代码展示:

    /*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function deleteDuplication(pHead)
    {
        // 思路:1,直接在原链表上进行修改
        if(!pHead) return null;
        let p =new ListNode(-1);
        p.next=pHead;    //添加虚拟头结点
        let pre=p;        //代指头结点
        let cur=p.next;    //当前结点
        
        while(cur){
            if(cur.next && cur.val==cur.next.val){
                while(cur.next && cur.val==cur.next.val){    //一直找到不同的点
                    cur=cur.next;
                }
                pre.next=cur.next;//因为是不保留删除,所以cur要再往下走一个
                cur=cur.next;    //更新cur为他的下一个
            }else{
                pre=pre.next;    
                cur=cur.next;
            }
        }
        return p.next;
        
        //2,新建一个链表,链接插入元素
        
        //3,使用集合,记录最后一个重复值,删除所有值
    	// if(pHead.next === null)
    	// return pHead;
    	// let p = pHead;
    	// let res = [];
    	// let tmp;
    	// let tmp2;
    	// while(p !== null){
    	//  if(res.indexOf(p.val) > -1){
    	//      tmp = p.val;
    	//      while(p.next && p.val === p.next.val){
    	//          p = p.next;
    	//      }
    	//      tmp = p.val;
    	//      p = p.next;
    	//  }else{
    	//      tmp2 = p.val;
    	//      if( tmp2 !== tmp){
    	//          for(let i=res.length-1;i>=0;i--){
    	//              if(res[i] === tmp){
    	//                  res.pop();
    	//              }
    	//          }
    	//      }
    	//      p = p.next;
    	//  }
    	// }
    	// let node = new ListNode(-1);
    	
    	// for(let i=0;i<res.length;i++){
    	//  node.val = res[i];
    	//  node = node.next;
    	// }
    	// return node;
    }
    
    
    展开全文
  • 删除链表中的节点 给定单链表的头指针和要删除的指针节点,在O(1)时间内删除该节点。 1.删除的节点不是尾部节点 - 将next节点覆盖当前节点 2.删除的节点是尾部节点且等于头节点,即只有一个节点 - 将头节点置为null...

    删除链表中的节点

    给定单链表的头指针和要删除的指针节点,在O(1)时间内删除该节点。

    • 1.删除的节点不是尾部节点 - 将next节点覆盖当前节点
    • 2.删除的节点是尾部节点且等于头节点,即只有一个节点 - 将头节点置为null
    • 3.删除的节点是尾节点且前面还有节点 - 遍历到末尾的前一个节点删除

    只有第三种情况时间复杂度是O(n),且这种情况只会出现1/n次,所以算法时间复杂度是O(1)

    var deleteNode = function (head, node) {
        if (node.next) {
            node.val = node.next.val;
            node.next = node.next.next;
        } else if (node === head) {
            node = null;
            head = null;
        } else {
            node = head;
            while (node.next.next) {
                node = node.next;
            }
            node.next = null;
            node = null;
        }
        return node;
    };
    

    删除链表中重复的节点

    方法1.存储链表中元素出现的次数

    • 1.用一个map存储每个节点出现的次数
    • 2.删除出现次数大于1的节点

    此方法删除节点时可以使用上面总结的办法。

    时间复杂度:O(n)

    空间复杂度:O(n)

    function deleteDuplication(pHead) {
        const map = {};
        if (pHead && pHead.next) {
            let current = pHead;
            // 计数
            while (current) {
                //通过键获取值
                const val = map[current.val];
                //如果不为0则加一;否则等于1
                map[current.val] = val ? val + 1 : 1;
                //取下一个节点
                current = current.next;
            }
            //链表处理
            current = pHead;
            while (current) {
                //获取当前节点的值
                const val = map[current.val];
                if (val > 1) {
                    // 删除节点
                    console.log(val);
                    if (current.next) {
                        current.val = current.next.val;
                        current.next = current.next.next;
                    } else if (current === pHead) {
                        current = null;
                        pHead = null;
                    } else {
                        current = pHead;
                        while (current.next.next) {
                            current = current.next;
                        }
                        current.next = null;
                        current = null;
                    }
    
                } else {
                    current = current.next;
                }
            }
        }
        return pHead;
    }
    

    方法2:重新比较连接数组

    链表是排好顺序的,所以重复元素都会相邻出现 递归链表:

    • 1.当前节点或当前节点的next为空,返回该节点
    • 2.当前节点是重复节点:找到后面第一个不重复的节点
    • 3.当前节点不重复:将当前的节点的next赋值为下一个不重复的节点
    function deleteDuplication(pHead) {
        if (!pHead || !pHead.next) {
            return pHead;
        } else if (pHead.val === pHead.next.val) {
            let tempNode = pHead.next;
            while (tempNode && pHead.val === tempNode.val) {
                tempNode = tempNode.next;
            }
            return deleteDuplication(tempNode);
        } else {
            pHead.next = deleteDuplication(pHead.next);
            return pHead;
        }
    }
    

    递归分析:

    1. 定义递归函数的功能:删除重复节点

    2. 结束条件:节点为空和next为空

    3. 等价表达式,缩小参数范围。

      pHead.next = deleteDuplication(pHead.next);

      return pHead

    时间复杂度:O(n)

    空间复杂度:O(1)

    更多资料

    整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

    📖数据结构专栏:剑指 Offer 题解 + JS 代码
    🐱Github笔记 :ruoruochen GitHub

    展开全文
  • 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点 示例: 给定一个链表: 1-&gt;2-&gt;3-&gt;4-&gt;5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1-&gt;2-&gt;3-&...

    版权声明:本文为博主原创文章,未经博主允许不得转载

    题目描述:

    给定一个链表,删除链表的倒数第 个节点,并且返回链表的头结点

    示例:
    给定一个链表: 1->2->3->4->5, 和 n = 2.
    当删除了倒数第二个节点后,链表变为 1->2->3->5.
    说明:
    给定的 n 保证是有效的。
    var removeNthFromEnd = function(head, n) {
        var length=0;
        var it=head;
        while(it){
            length++;
            it=it.next
        }    
        n=length-n;
        it=head
        if(n==0){
            return head.next;
        }
        else{
            while(n>1){
                it=it.next;
                n--
            }
            it.next=it.next.next
        }
        return head
    };

     

    展开全文
  • 要点:使用哑节点对应需要删除链表第一个节点情况 优化:单次遍历:使用快慢指针。快慢指针的使用又打开了新世界大门! 第一种方法:遍历两次 var removeNthFromEnd = function(head, n) { let tail = head let...
  • 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 示例: 给定 1-&gt;2-&gt;3-&gt;4, 你应该返回 2-&gt;1-&gt;4-&gt;3 .说明: 你的算法只能使用常数的额外空间。 你不能...
  • 给定一个链表,删除链表的倒数第 nn 个节点并返回链表的头指针 例如, 给出的链表为: 1\to 2\to 3\to 4\to 51→2→3→4→5, n= 2n=2. 删除了链表的倒数第 nn 个节点之后,链表变为1\to 2\to 3\to 51→2→3→5. 备注:...
  • 删除链表中的节点⚡️ 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。 现有一个链表 – head = [4,5,1,9],它可以表示为: 示例 1: 输入:head = [4,5,1,9]...
  • 删除链表节点

    2021-06-23 16:01:37
    删除链表的节点 题目描述 给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。 返回删除后的链表的头节点。 注意:此题对比原题有改动 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] ...
  • js代码-5.1 删除链表倒数第n个节点 快慢指针
  • 主要介绍了JavaScript 双向链表操作,结合实例形式分析了JavaScript双向链表的创建、增加、查找、删除等相关操作技巧,需要的朋友可以参考下
  • 删除链表中的节点 JavaScript解决问题描述代码 问题描述 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。 示例 1: 输入:head = [4,5,1,9], node = 5 输出...
  • 测试代码 //构造链表 var head = new sNode(0); var nums = [2,2,1,1,3,3,3,1,2,2,3,3]; console.log(head); for(var i=0;i;i++){ var p = new sNode(nums[i]); p.pNext = he
  • 如果下一个值等于val,则删除下一个值 使用了ES6的?.运算符 代码 const deleteNode = (head, val) => { // 定义虚拟节点 const res = new ListNode(-1); // 虚拟节点连接到head res.next = head; // 定义p...
  • 删除链表中的节点 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。 现有一个链表 – head = [4,5,1,9],它可以表示为: 示例 1: 输入:head = [4,5,1,9],...
  • 删除链表中重复的节点 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5 思路 1.因为...
  • "end 输出链表数据..." ); writeEnd(); } //产生整型随机数 function randInt (max) { return parseInt ( Math .random()*max); } //对默认的输出进行封装为write函数 function write (str) { ...
  • 删除链表的节点 JavaScript 实现问题描述代码 问题描述 给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。 返回删除后的链表的头节点。 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,...
  • 删除链表的倒数第N个节点 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3-&...
  • 在一个排序的链表中,存在重复的结点,请删除链表中重复的结点,重复的结点不保留,返回链表头指针。例如,链表1->2->3->3->4->4->5 处理后为 1->2->5。 二、预设数据结构 function ...
  • Js实现链表操作

    千次阅读 2020-05-13 11:57:27
    JavaScript实现链表主要操作,包括创建链表、遍历链表、获取链表长度、获取第i个元素值、获取倒数第i个元素值、插入节点、删除节点、有序链表合并、有序链表交集。 创建链表 class Node{ constructor(data){ this....
  • 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1-&gt;2-&gt;3-&gt;4-&gt;5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1-&gt;2-&gt;3...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,028
精华内容 6,411
关键字:

js删除链表