力扣算法|力扣算法（删除排序链表中的重复元素Ⅱ）链表|leetcode

力扣算法：删除排序链表中的重复元素Ⅱ

一、力扣算法：删除排序链表中的重复元素Ⅱ
- 1、问题
- 2、思路
- 3、解题代码
- 4、时间与空间复杂度
备注

一、力扣算法：删除排序链表中的重复元素Ⅱ 1、问题存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。
返回同样按升序排列的结果链表。
示例 1：

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

文章图片

示例 2：

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

文章图片

提示：

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

2、思路

因为头节点可能会被删除，我们在头节点前添加一个节点，便于后续操作。
设置一个cur指针指向添加节点后的 head，设置一个变量 x 用来保存遍历过程中的 “重复节点值” 。
设置 cur.next 和 cur.next.next 的存在为循环结束条件，当二者有一个不存在时说明链表没有去重复的必要了。
当 cur.next.val 和 cur.next.next.val 相等时说明需要去重，因为后续可能还有多个相同值节点，所以将 cur.next.val 保存至 x , 并建立一个循环，对节点进行遍历，如果节点值与x相等，则将 cur 的“下一个”指针指向“下一个的下一个”，这样就能达到去重复的效果。
如果不相等则 node 移动到下一个位置继续循环。
最终返回 head.next。

3、解题代码

#coding:utf-8 # Definition for singly-linked list. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def deleteDuplicates(self, head: ListNode) -> ListNode: head = ListNode(0, head) cur = head while cur.next and cur.next.next: if cur.next.val == cur.next.next.val: x = cur.next.val while cur.next and cur.next.val == x: cur.next = cur.next.next else: cur = cur.next return head.nextif __name__ =="__main__": #建立链表 def build_link(head): li = cur = ListNode(None) for i in head: cur.next = ListNode(i) cur = cur.next return li.nexthead = [1, 1, 1, 2, 3] # head = [] head = build_link(head)#删除重复元素 solution = Solution() res = solution.deleteDuplicates(head)#打印链表 nums = [] while res: nums.append(res.val) res = res.next print(nums)

4、时间与空间复杂度时间复杂度：O(N)
空间复杂度：O(1)
备注 1、问题来自：
【力扣算法|力扣算法（删除排序链表中的重复元素Ⅱ）】力扣（LeetCode）
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii