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

简介: 存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次 。返回同样按升序排列的结果链表。

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指向新链表的头指针)

代码运行结果为:

网络异常,图片无法展示
|

4. 结构讲解

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

链表

链表是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接链表的结构:data为自定义的数据,next为下一个节点的地址。

基本元素

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

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

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

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

相关文章
|
2月前
|
程序员
【刷题记录】移除链表元素
【刷题记录】移除链表元素
01_移除链表元素
01_移除链表元素
|
2月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
2月前
|
存储 C语言
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
|
3月前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
34 2
【数据结构OJ题】移除链表元素
|
2月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
20 0
|
2月前
|
Python
【Leetcode刷题Python】203.移除链表元素
文章提供了三种删除链表中特定值节点的方法:迭代法、虚拟节点迭代删除法和递归法,并给出了相应的Python实现代码。
16 0
|
3月前
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
25 0
|
4月前
|
算法
【数据结构与算法 刷题系列】移除链表元素
【数据结构与算法 刷题系列】移除链表元素
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表