82. 删除排序链表中的重复元素 II 题目 我的思路 题解1 - 快慢指针 题解2 - 递归 总结
<>
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5 输出: 1->2->5
示例 2:
输入: 1->1->1->2->3 输出: 2->3
我的思路
(误)
1.建立虚拟节点node，使node.next = head
2.用快指针来检查相等的两个节点fast和fast.next，相等则跳过这两个节点。（误）
这一步有思维漏洞，比如对于链表 1, 2, 2, 2, 3 就会有2遗留消除不掉
3.链接满指针和快指针，跳过重复节点
用图说明：
class Solution(object): def deleteDuplicates(self, head): node = ListNode(-1) node.next = head slow = node fast = node.next while fast: #如果不加fast.next的判断 ，对于样例 [1] 会出错 if fast.next and fast.val == fast.next.val: #(误)这个跳过重复项的方法有问题 fast = fast.next.next else: slow.next = fast slow = fast fast = fast.next return node.next
题解1 - 快慢指针
class Solution(object): def deleteDuplicates(self, head): node = ListNode(-1) node.next = head slow = node fast = node.next while fast: if fast.next and fast.val == fast.next.val: tmp = fast.val while fast and tmp == fast.val: fast = fast.next else: slow.next = fast slow = fast fast = fast.next #考虑到 1, 1, 1 这样的样例 slow.next = fast return node.next
题解2 - 递归
理解不能。。。。。。。