题目

难度：★☆☆☆☆
类型：链表

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

解答

这是链表中的基础题，删除排序链表中重复元素，需要遍历链表，并将后面和当前相等的结点删去，这里为了帮助大家理解，特地增加了创建链表函数（create_linked_list）和打印链表函数（print_linked_list）。

class Solution:
    def deleteDuplicates(self, head):
        cur = head                          # 定义临时结点
        while cur and cur.next:             # 当前结点和下一个结点有效时
            if cur.val == cur.next.val:     # 如果当前结点的值等于下一个结点的值
                cur.next = cur.next.next    # 去掉下一个结点
            else:
                cur = cur.next              # 否则当前结点后移
        return head                         # 返回头结点


class ListNode:
    """
    链表节点
    """
    def __init__(self, x):          # 在创建结点时，执行初始化赋值程序
        self.val = x                # 当前结点的值
        self.next = None            # 下一个节点，刚创建时为None


def create_linked_list(nums):
    """
    创建链表
    :param nums: 输入代表里链表的数字列表
    :return: 返回创建好的链表的头结点，可以得到整个链表的所有信息
    """
    if not nums:                        # 输入空列表
        return
    head = prev = ListNode(nums[0])     # 第一个结点
    for num in nums[1:]:
        tmp = ListNode(num)             # 创建当前结点
        prev.next = tmp                 # 挂在已经创建好的链表末尾
        prev = prev.next                # 指针后移
    return head


def print_linked_list(head):
    """
    打印链表
    :param head: 要打印的链表的头结点
    :return: 结点值列表
    """
    nums = []
    while head:
        nums.append(head.val)
        head = head.next
    print(nums)
    return nums


if __name__ == "__main__":
    h = create_linked_list([1, 2, 3, 3, 3, 4, 5, 6, 6])     # 创建链表
    s = Solution()                                          # 实例化解决方案
    r = s.deleteDuplicates(h)                               # 调用去重方法
    print_linked_list(r)                                    # 打印链表