首页 > 试题广场 >

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

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

热度指数：179658 时间限制：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，点此查看相关信息

算法知识视频讲解

srcrs

1.保存三个节点值pre,cur,next，初始化pre和cur想等，需要特殊处理

2.从cur开始遍历，判断cur和next的值是否相等，如果相等则找到这个值

3.重新再走一遍当前循环，删除和这个值相等的节点，删除时需要区分是头节点还是中间节点

4.周而复始直到所有节点遍历完

func deleteDuplicates( head *ListNode ) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    delVal := -1001
    pre, cur, next := head, head, head.Next
    
    for cur != nil {
        if cur.Val == delVal {
            if pre == cur {
                cur, head, pre = next, next, pre.Next
            } else {
                pre.Next, cur = next,next
            }
            if next != nil {
                next = next.Next
            }
            continue
        }
        if next != nil && cur.Val == next.Val {
            delVal = cur.Val
            continue
        } else {
            delVal = -1001
        }
        pre, cur = cur, next
        if next != nil {
            next = next.Next
        }
    }
    return head
}

发表于 2022-06-17 00:39:59 回复(0)

风轻云淡.

func deleteDuplicates( head *ListNode ) *ListNode {
    // write code here
    Head:=new(ListNode)
    Head.Next=head
    pre:=Head
    tmp:=head
    isUnique:=true
    for tmp!=nil && tmp.Next!=nil{
        if tmp.Val==tmp.Next.Val{
            isUnique=false
            tmp.Next=tmp.Next.Next
        }else{
            if !isUnique{
                isUnique=true
                pre.Next=tmp.Next
                tmp=pre.Next
            }else{
                pre=pre.Next
                tmp=tmp.Next
            }
        }
    }
    if !isUnique{
        pre.Next=tmp.Next
    }
    return Head.Next
}

发表于 2022-04-21 15:37:27 回复(0)

admxt

func deleteDuplicates( head *ListNode ) *ListNode {
if head==nil{
return head
}
c:=head
if c.Next==nil{
return head
}
if c.Val!=c.Next.Val{
c.Next=deleteDuplicates(c.Next)
}else{
for c.Next!=nil&&c.Val==c.Next.Val{
c=c.Next
}
head=deleteDuplicates(c.Next)
}
return head
// write code here
}

发表于 2022-03-03 15:53:48 回复(0)

bigkai

package main
import . "nc_tools"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/

/**
*
* @param head ListNode类
* @return ListNode类
*/
func deleteDuplicates( head *ListNode ) *ListNode {
    if head == nil || head.Next == nil {return head}
    newList := &ListNode{head.Val - 1, nil}
    newList.Next = head
    dummy, cur := newList, head
    for cur != nil && cur.Next != nil {
        if cur.Val != cur.Next.Val {
            dummy = cur
        } else {
            for cur.Next != nil && cur.Val == cur.Next.Val {
                cur = cur.Next
            }
            dummy.Next = cur.Next
        }
        cur = cur.Next
    }
    return newList.Next
}

发表于 2021-08-08 07:34:03 回复(0)