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

Question

我已考虑了3个解决方案的案件如下：

情况1:如果数组为表格1、2、3、4、5 1,1,1,2,3,4,5

• CASE 1,2,3,3,3,3,4,5

2: If数组为表单

• 3: If数组为表单1，2，3，3，3，3，4，5

我的解决方案到了。

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

乍一看，它看起来很琐碎，但是在深入研究它之后，问题实际上是非常烦人的。你得考虑三个案子。元素可以在前面重复。除非你找到单一的元素，否则你必须搜索头部。另外两种情况都可以用一个算法来解决，因为设置节点旁边的零并不重要。

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)
}

Answer 2

通过分别解决每个案例，您的解决方案过于复杂了。如果你在重复：

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
  }
}