删除链表中重复的结点

注意：

书上有个如何在o(1)情况下删除结点的问题

---

最初思路：
使用一个额外的list记录出现的元素，遍历，再遇到相同的就删除。
有个问题：如何删除第一次出现的元素？
先遍历一遍，用list保存所有元素；
再遍历一遍，如果在list里出现次数大于1，就删除。

class Solution:
    def deleteDuplication(self, pHead):
        if pHead == None:
            return pHead
        temp = [] #保存所有的元素
        p = pHead
        
        while p != None:
            temp.append(p.val)
            p = p.next
        p = pHead
        while p != None:
            if temp.count(p.val) > 1: #是重复元素
                pHead = self.delNode(pHead,p)
            p = p.next
        return pHead
          
    def delNode(self, pHead, pnode):
        if pHead == pnode:#删除头结点
            return pHead.next
        p = pHead
        if p.next != pnode:
            p = p.next
        p.next = p.next.next
        return pHead

以上的代码没注意到是排序的数组

不使用辅助list

class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if pHead == None:
            return pHead
        p = pHead
        first =ListNode(-1)
        first.next = p #
        pre = first #pre是当前结点的前一个位置
        # 如果phead是重复结点
        while p != None and p.next != None:
            if p.val == p.next.val:
                tempval = p.val
                while p and p.val == tempval:
                    p = p.next
                pre.next = p #直接跳过重复的结点
            else:
                pre = p
                p = p.next
        return first.next