分类刷题：链表的删除

分类编程打卡第1天：

JZ18 删除链表的节点

    def deleteNode(self , head: ListNode, val: int) -> ListNode:
        #加入一个头节点
        res = ListNode(0)
        #将头节点挂靠到原始头节点
        res.next = head
        #如果不定义这个让pre去操作，最后输出res将是一个数字（即node.val）
        #指针移动了，不开一个，无法找到链表头返回
        pre = res
        #其实这一步可以省略，因为最后输出的是pre相关的res
        cur = head
        while cur:
            if cur.val == val:
                pre.next = cur.next
            pre = cur
            cur = cur.next
        return res.next

Leetcode83. 删除排序链表中的重复元素

题目描述：

输入：head = [1,1,2] 输出：[1,2]

输入：head = [1,1,2,3,3] 输出：[1,2,3]

直接遍历

    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return None
        cur = head
        while cur.next:
            if cur.val == cur.next.val:#判断当前位置是否为重复数据
                cur.next = cur.next.next#如果是的话探索之后的数据是否为相同的数据
            else:
                cur = cur.next#如果当前位置非重复数据就下一个
        return head

快慢指针

    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return None
        slow = fast = head
        while fast:
            if slow.val != fast.val:
                slow.next = fast
                slow = slow.next #slow后移
            fast = fast.next #fast后移
        slow.next = None
        return head

JZ76 删除链表中重复的结点

题目描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

注意：链表已被排序，所以若有重复节点则是至少两个连续的

方法1：直接比较删除法

    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        #空链表
        if pHead == None: 
            return None
        res = ListNode(0)
        #在链表前加一个表头
        res.next = pHead 
        cur = res
        while cur.next and cur.next.next:  #要从cur.next开始是因为cur.next才是pHead,只有这样才能从头遍历
            #遇到相邻两个节点值相同
            if cur.next.val == cur.next.next.val: 
                temp = cur.next.val
                #将所有相同的都跳过，因为cur.next = cur.next.next指针不断地往后移所以是有可能让cur.next = None的，所以要避免这种情况发生
                while cur.next != None and cur.next.val == temp: 
                    cur.next = cur.next.next
            else:
                cur = cur.next
        #返回时去掉表头
        return res.next

注意：

这一题与Leetcode83. 删除排序链表中的重复元素很类似，不同点在于本题要把重复的元素删干净，而Leetcode要保留一个。

下面系统的重新看一遍三种类型的不同点：

1. 删干净：(自己复现的过程)

第一遍自己写：首先参考了83的代码：

    def deleteDuplication(self , pHead: ListNode) -> ListNode
        if pHead == None: 
            return None
        cur = pHead 
        while cur.next: 
            if cur.val == cur.next.val: 
                temp = cur.val
                while cur.next != None and cur.next.val == temp: 
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return pHead

输出的结果并没有把重复元素全部删干净，原因在于比如[1,2,2,3,4,5]在遍历到第一个2的时候，cur=2, cur.next=2, temp=2, cur.next将跳到3，而返回if判断语句发现2！=3，所以跳到else判断语句，继续保留2。以至于最后的输出实际上是原来的pHead。

第二遍修正：

    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        #空链  
        if pHead == None: 
            return None
        res = ListNode(0)
        res.next = pHead
        cur = res 
        while cur.next and cur.next.next: 
            if cur.next.val == cur.next.next.val: 
                temp = cur.next.val
                while cur.next != None and cur.next.val == temp: 
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return res.next

注意：继续以[1,2,2,3,4,5]为例，在遍历到1的时候就已经开始判断2和2是否相等了，2=2，temp=2,继续向后遍历，只要没到最后，且还有重复元素，接着因为cur.next已经调到了第二个2，依然满足2=temp，所以cur.next跳到了3，不再满足while条件，故推出进入else,所以把3给保存上了。

核心在于可以把cur.next剥离出来作为一个单独的考虑因素去进行处理，那么就不会影响到cur

更好理解的解法3：

    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        # 定义头节点指针，前指针和当前指针
        p0 = ListNode(-1)
        p0.next = pHead
        p = p0 
        cur = pHead
        # 循环遍历
        while cur and cur.next:
            # 不相等，则前后指针继续遍历
            if cur.val != cur.next.val:
                p = p.next
                cur = cur.next
            else:
                # 出现重复节点，即当前指针节点与下一个节点相等，则cur继续向右判断
                val = cur.val
                while cur and cur.val == val:
                    cur = cur.next
                p.next = cur
        return p0.next

2. 只剩1个：

直接遍历

    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return None
        cur = head
        while cur.next:
            if cur.val == cur.next.val:#判断当前位置是否为重复数据
                cur.next = cur.next.next#如果是的话探索之后的数据是否为相同的数据
            else:
                cur = cur.next#如果当前位置非重复数据就下一个
        return head

方法2： 哈希表

    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        #空链表
        if pHead == None: 
            return None
        mp = dict()
        cur = pHead
        #遍历链表统计每个节点值出现的次数
        while cur: 
            if cur.val in mp:
                mp[cur.val] += 1
            else:
                mp[cur.val] = 1
            cur = cur.next
        res = ListNode(0)
        #在链表前加一个表头
        res.next = pHead 
        cur = res
        #再次遍历链表
        while cur.next: 
            #如果节点值计数不为1
            if mp[cur.next.val] != 1: 
                #删去该节点
                cur.next = cur.next.next 
            else:
                cur = cur.next
        #去掉表头
        return res.next 

注意：要熟练掌握构建哈希表的方法