我考虑了3种解决方案的情况:
- 情况1:如果数组的形式为[1,2,3,4,5]
- 情况2:如果数组的形式为[1,1,2,3,4,5]
- 情况3:如果数组的形式为[1,2,3,3,4,5]
我在Go中的解决方案。
type ListNode struct {
Val int
Next *ListNode
}
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil || head.Next ==nil{
return head
}
current := head
var prev *ListNode
for current.Next != nil {
if current.Val != current.Next.Val{ // (CASE-1)
prev = current
current = current.Next
} else if current ==head && current.Val == current.Next.Val { //(CASE-2)
current = current.Next.Next
head = current
} else if current != head && current.Val == current.Next.Val { //(CASE-3)
for current.Val == current.Next.Val{
current = current.Next
}
temp := current.Next
prev = temp
current = prev.Next
}
}
return head
}
我在CASE-3中遇到问题?我不知道我做错了什么。
通过分别解决每个案例,您的解决方案过于复杂。如果您正在进行重复数据消除:
current:=head
for current.Next!=nil {
if current.Next.Val==current.Val {
// Remove the duplicate node, stay on the same node
curent.Next=current.Next.Next
} else {
// Advance to the next node
current=current.Next
}
}
如果要删除重复值的所有实例:
current:=head
var prev *ListNode
for current!=nil {
trc:=current
// Find the next node with a different value
for trc!=nil {
if trc.Val==current.Val {
trc=trc.Next
} else {
break
}
}
// if trc==nil, all remaining values are the same
// if prev is also nil, all values in the list are the same
if trc==nil {
if prev==nil {
// All values in the list are the same
} else {
prev.Next=nil
current=nil
}
} else if trc==current {
// Not a duplicate entry
prev=current
current=current.Next
} else {
if prev!=nil {
prev.Next=trc.Next
} else {
// you need to set head = trc.Next
}
current=trc.Next
}
}
乍一看,它看起来微不足道,但深入研究后,这个问题实际上真的很烦人。你必须考虑三种情况。元素可以在前面重复。除非你找到一个元素,否则你必须搜索头部。其他两种情况可以通过一种算法解决,因为将节点设置为零并不重要。
package main
import "fmt"
type LL struct {
Val int
Next *LL
}
func removeDuplicates(h *LL) (res *LL) {
current := h
var prev *LL
// annoying
if current.Next == nil {
return current
}
// even more annoying
if current.Next.Val != current.Val {
res = current
}
for current.Next != nil {
if current.Next.Val == current.Val {
current.Next = current.Next.Next
// trailing case - most annoying of them all
if prev != nil && (current.Next == nil || current.Next.Val != current.Val) {
prev.Next = current.Next
}
} else {
prev = current
current = current.Next
// front repetition - decently annoying
if res == nil && (current.Next == nil || current.Next.Val != current.Val) {
res = current
}
}
}
return
}
func main() {
l := &LL{1, &LL{1, &LL{2, &LL{2, &LL{3, &LL{4, &LL{4, &LL{5, &LL{6, &LL{6, nil}}}}}}}}}}
l = removeDuplicates(l)
current := l
for current != nil {
fmt.Print(current.Val)
current = current.Next
}
fmt.Println(l)
}