删除排序链表中的重复元素-python

leetCode第83题，删除排序链表中的重复元素

示例1：

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

示例2：

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

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

题目已经说明了链表本身是升序的，那么前后最多只有重复的情况，而不会有后面比前面小的情况，那么只要将链表遍历，碰到前后相等的情况，直接把后一个元素删掉即可

# python3
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head == None:
            return head
        currentNode = head
        while currentNode.next != None :
            if currentNode.next.val == currentNode.val:
                currentNode.next = currentNode.next.next
            else:
                currentNode = currentNode.next
        return head

当我们编写代码时，能感觉到，从前往后一个一个元素拼接成新的有序表时，实际上是拼完一个元素后和一个更短的链表做相同的操作，那么我们不妨试试递归的方法。
如果头指针是空，或者头指针的下一个是空，直接返回头指针。
如果头指针的下一个非空，那么头指针和头指针之后的链表做拼接，直接调用自身。head.next = self.deleteDuplicates(head.next)
对于返回的head.next链表部分，如果它的值和head.val相等，那么直接将head丢弃，返回head.next。否则不做处理，返回head。

# python3
class Solution1:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        head.next = self.deleteDuplicates(head.next)
        if head.val == head.next.val:  # 如果后一个比和前一个一样大，那么只返回后一个
            return head.next
        else:     #  前一个比后一个小，满足要求，直接返回
            return head