从排序列表中删除重复项 - 列码 -82

Question

我考虑了3种解决方案的案例：

• 案例 1 ： 如果数组的形式为 [1，2，3，4，5]

• 案例 2 ： 如果数组的形式为 [1，1，1，2，3，4，5]

• 情况 3 ： 如果数组是 [1，2，3，3，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 

}  

我在案例-3中遇到问题？我不知道我做错了什么。

Answer 1

通过单独解决每个案例，您的解决方案过于复杂。如果要进行重复数据删除：current:=headfor 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:=headvar prev *ListNodefor 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  }}

Answer 2

乍一看，它看起来微不足道，但在深入研究之后，问题实际上真的很烦人。您必须考虑三种情况。元素可以在前面重复。除非你找到单个元素，否则你必须搜索头部。其他两种情况可以通过一种算法解决，因为节点的nil旁边设置并不重要。package mainimport "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)}