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值