删除链表中重复的节点

题目描述

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

思路

思路1： 简单粗暴。先遍历整个链表，把链表里的元素放进一个数组中，然后对数组进行过滤，只保留出现一次的元素。把筛选后的数组里的元素重新构建成链表。
思路2： 递归。当当前的节点与下一个点相同时，一直向后找，找到不同的点，返回。当 当前的节点与下一个点不同时，判断对后一个点递归判断。当检测到尾部时，返回尾部。

代码

常规

def deleteDuplication(self, pHead):
        node_list = []
        while pHead is not None:
            node_list.append(pHead.val)
            pHead = pHead.next
        clean_node_list = list(filter(lambda x:node_list.count(x)==1,node_list)) #过滤重复node
        fake_node = ListNode(0)  #辅助node
        pre = fake_node
        for i in range(len(clean_node_list)):
            temp_node = ListNode(clean_node_list[i])
            pre.next = temp_node
            pre = temp_node
        return fake_node.next

递归

def deleteDuplication(self, pHead):
        if pHead is None:
            return pHead #如果是空结点
        if pHead.next is None:
            return pHead #递归的尽头
        if pHead.val == pHead.next.val:
            #当前点与下一个点相同
            #一直向后找，直到找到不同的点
            temp_node = pHead.next
            while temp_node is not None and temp_node.val == pHead.val :
                #注意判断顺序，要先判断非空，再判断value
                temp_node = temp_node.next
            return self.deleteDuplication(temp_node) 
        else:
            #pHead.val ！= pHead.next.val
            pHead.next = self.deleteDuplication(pHead.next)
            #当前点与下一个点不等，但不确定下一个点与它后面的点不等
            return pHead