首页 > 试题广场 >

删除有序链表中重复的元素-II

[编程题]删除有序链表中重复的元素-II

热度指数：215580 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为 $1 \to 2\to 3\to 3\to 4\to 4\to5$ , 返回 $1\to 2\to5$ .
给出的链表为 $1\to1 \to 1\to 2 \to 3$ , 返回 $2\to 3$ .

数据范围：链表长度 $0 \le n \le 10000$ ，链表中的值满足 $|val| \le 1000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,2}

输出

{1}

示例2

输入

{}

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

JavaScript Node

牛客CyNcu

function ListNode(x) {

this.val = x;

this.next = null;

}

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param head ListNode类

* @return ListNode类

function deleteDuplicates(head) {

// write code here

let arr = [];

let arr2 = [];

let res = null;

while (head) {

let index = arr.includes(head.val);

if (index) {

arr2.push(head.val);

} else {

arr.push(head.val);

}

head = head.next;

}

arr = arr.filter((item) => {

return !arr2.includes(item)

}).sort((a,b)=>b-a)

for (let i = 0; i < arr.length; i++) {

let node = new ListNode(arr[i]);

node.next = res;

res = node;

}

return res;

}

module.exports = {

deleteDuplicates: deleteDuplicates

};

发表于 2024-07-12 17:09:50 回复(0)

JavaScript Node

piku99

function deleteDuplicates( head ) {
   let map = new Map()
   let p = head
   while(p){
       if(!map.has(p.val)){
           map.set(p.val,1)
       }else{
           let tmp = map.get(p.val)
           tmp++
           map.set(p.val,tmp)
       }
       p = p.next
   }
   let node = new ListNode(0)
   node.next = head  
   let cur = node
   while(cur.next !== null){
       if(map.get(cur.next.val) !== 1){
           cur.next = cur.next.next
       }else{
           cur = cur.next
       }
   }
   return node.next
}v

发表于 2022-11-03 20:23:38 回复(0)

JavaScript Node

♈FourBrother✅已认证♉

// 思路：当前节点值跟上个节点和下个节点都不重复的时候，就是符合要求的

function deleteDuplicates( head ) {
    // write code here
    let newHead = null
    let newPre = null
    let cur = head
    let preVal = null
    while (cur) {
        const next = cur.next
        if (cur.val !== preVal && (!next || next.val !== cur.val)) {
            const node = {
                val: cur.val,
                next: null
            }
            if (newPre === null) {
                newHead = node
                newPre = node
            } else {
                newPre.next = node
                newPre = node
            }
        }
        preVal = cur.val
        cur = next
    }
    return newHead
}

发表于 2021-11-18 16:38:10 回复(0)