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

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

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

一、力扣算法：删除排序链表中的重复元素 1、问题存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素只出现一次。
返回同样按升序排列的结果链表。
示例1：

文章图片

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

示例2：

文章图片

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

提示：

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

2、思路思路1：（遍历方法）

建立一个node指针指向链表头部 head。
设置 node 和 node.next 的存在为循环结束条件，当二者有一个不存在时说明链表没有去重复的必要了。
当 node.val 和 node.next.val 相等时说明需要去重，则将 node 的“下一个”指针指向“下一个的下一个”，这样就能达到去重复的效果。
如果不相等则 node 移动到下一个位置继续循环。

思路1：（递归方法）

设置递归终止条件：当 head 不存在或者 head.next 不存在，直接返回 head。
无论 head.val 和 head.next.val 是否相等，head.next 一定等于后续链表的去重，即 self.deleteDuplicates(head.next) 。

原因：

当 head.val != head.next.val 时，head 节点要保留，所以 head.next = self.deleteDuplicates(head.next) 比较好理解，因为要把后面去重的链表拼接到当前 head 节点之后。
当 head.val == head.next.val 时， head 节点要删除，所以 return head.next ，如果我们不把 head.next = self.deleteDuplicates(head.next)，那么 return 的结果是原始 head.next ，所以仍然是没去重。

返回结果：

当 head.val != head.next.val 时， head 节点要保留，所以 return head 。
当 head.val == head.next.val 时， head 节点要删除，所以 return 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 = nextclass Solution: #遍历方法删除链表重复元素 def deleteDuplicates1(self, head: ListNode) -> ListNode: node = head while node and node.next: if node.val == node.next.val: node.next = node.next.next else: node = node.next return head#递归方法删除链表重复元素 def deleteDuplicates2(self, head): if not head or not head.next: return head head.next = self.deleteDuplicates2(head.next) return head if head.val != head.next.val else 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, 2, 3, 3] head = build_link(head)#删除重复元素 solution = Solution() res1 = solution.deleteDuplicates1(head) res2 = solution.deleteDuplicates2(head)#打印链表 nums1 = [] nums2 = [] while res1 and res2: nums1.append(res1.val) nums2.append(res1.val) res1 = res1.next res2 = res2.next print(nums1,nums2)

4、时间与空间复杂度 1、遍历方法
时间复杂度：O(N)。遍历链表的每个节点
空间复杂度：O(1)。只使用常量的空间
2、递归方法
时间复杂度：O(N)。链表的每个节点都访问一次
空间复杂度：O(N)。递归调用时用到系统的栈
备注 【力扣算法|力扣算法（删除排序链表中的重复元素）】转载：
1、力扣（LeetCode）
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
2、fuxuemingzhu
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/solution/fu-xue-ming-zhu-di-gui-die-dai-4-chong-d-t3bp/