本文讲述了python基础编程100例：第52期-基础结构：链表 删除排序链表中的重复元素！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第52期-基础结构：链表 删除排序链表中的重复元素

1 问题描述

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

示例 1:

输入: head = [1,1,2]

输出: [1,2]

示例 2:

输入: head = [1,1,2,3,3]

输出: [1,2,3]

示例 3:

输入: head = []

输出: []

初始代码

# Definition for singly-linked list.

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

 

class LinkList:

    def __init__(self):

        self.head=None

 

    def initList(self, data):

        while len(data)==0:return None

        self.head = ListNode(data[0])

        r=self.head

        p = self.head

        for i in data[1:]:

            node = ListNode(i)

            p.next = node

            p = p.next

        return r

    def printlist(self,head):

        a=[]

        if head == None: return []

        node = head

        while node != None:

            a.append(node.val)

            node = node.next

        return a

class Solution:

    def deleteDuplicates(self, head: ListNode) -> ListNode:

        #在此填写代码

if __name__ == '__main__':

    print(LinkList().printlist(Solution().deleteDuplicates(LinkList().initList([1,1,2]))))

    print(LinkList().printlist(Solution().deleteDuplicates(LinkList().initList([1,1,2,3,3]))))

    print(LinkList().printlist(Solution().deleteDuplicates(LinkList().initList([]))))

2 解题思路

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

当遍历完整个链表之后，我们返回链表的头节点即可。

3 解题方法

# Definition for singly-linked list.

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

 

class LinkList:

    def __init__(self):

        self.head=None

 

    def initList(self, data):

        while len(data)==0:return None

        self.head = ListNode(data[0])

        r=self.head

        p = self.head

        for i in data[1:]:

            node = ListNode(i)

            p.next = node

            p = p.next

        return r

    def printlist(self,head):

        a=[]

        if head == None: return []

        node = head

        while node != None:

            a.append(node.val)

            node = node.next

        return a

class Solution:

    def deleteDuplicates(self, head: ListNode) -> ListNode:

        b=ListNode(0)

        c=b

        while head:

            c.next=head

            while head.next and head.val==head.next.val:

                head.next=head.next.next

            head=head.next

            c=c.next

        return b.next

if __name__ == '__main__':

    print(LinkList().printlist(Solution().deleteDuplicates(LinkList().initList([1,1,2]))))

    print(LinkList().printlist(Solution().deleteDuplicates(LinkList().initList([1,1,2,3,3]))))

    print(LinkList().printlist(Solution().deleteDuplicates(LinkList().initList([]))))

第1-30，44-47行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑（具体为创建链表以及列表、链表转换）

第31行： 创建初始链表b，头指针数值为0

第32行： 保存头指针于变量c上，移动的是b指针

第33行： 当head不为None时，循环直到遍历完整个链表（print(None)的结果为False）

第34行： c链表的next指向head链表

第35行： 判断head.next是否非空，若非空，再判断其数值是否与head相等

第36行： 若数值相等，跳过head.next，并将head.next之后的链表head.next.next进行循环判断

第37行： 当两者数值不相等时，将head指向head.next（此时head.next已经指向与head数值不相等的链表上了）

第38行： c指针移到c.next，用于为c.next赋值后面的链表

第39行： 返回b.next（q.next指向新链表的头指针）

代码运行结果为：

结构讲解

这里用到了基础结构：链表，简单讲解下这个链表：

链表

链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接

链表的结构：data为自定义的数据，next为下一个节点的地址。

基本元素

节点：每个节点有两个部分，左边称为值域，存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。

head:head节点永远指向第一个节点

tail: tail永远指向最后一个节点

None:链表中最后一个节点的指针域为None值

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。