文章目录
- 82. 删除排序链表中的重复元素 II：
-
- 样例 1：
- 样例 2：
- 提示：
- 分析：
- 题解：
-
- rust：
- go：
- c++：
- python：
- java：
82. 删除排序链表中的重复元素 II：
给定一个已排序的链表的头 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- 题目数据保证链表已经按升序 排列
分析：
- 面对这道算法题目，二当家的再次陷入了沉思。
- 这道题目和 83. 删除排序链表中的重复元素 很像，但是要难一些。
- 同样是有序的，所有相同数值的节点会连在一起。
- 同样链表有可能不存在任何节点，不用做任何处理。
- 但是由于是要删除 所有重复数字的节点 ，也就是说不能仅仅比较当前节点和下一个节点，而是要比较下一个节点和下下一个节点的值，因为下一个节点也是有可能要删除的，而单向链表又仅仅只能单向遍历，所以必须保留要删除节点的前一个节点的指针，尤其要注意的就是头节点也是有可能要被删除的，但是它显然没有前一个节点，为了能统一处理，一般是建立一个虚拟节点（也可以叫做哑节点，或者哨兵节点），当作头节点，这样就可以统一处理流程。
- 同样要对rust说两句，可能是我的水平太差了，rust的题解写的超级长，非常啰嗦，但是那又怎么样，安全第一，rust是最棒的，难学一点是应该的，有本事你改良它。
题解：
rust：
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn delete_duplicates(head: OptionBoxListNode>>) -> OptionBoxListNode>> {
if head.is_none() {
return head;
}
let mut dummy = Option::Some(Box::new(ListNode::new(0)));
dummy.as_mut().unwrap().next = head;
let mut cur = dummy.as_mut().unwrap();
while cur.next.is_some() && cur.next.as_ref().unwrap().next.is_some() {
if cur.next.as_ref().unwrap().val == cur.next.as_ref().unwrap().next.as_ref().unwrap().val {
let v = cur.next.as_ref().unwrap().val;
while cur.next.is_some() && cur.next.as_ref().unwrap().val == v {
cur.next = cur.next.as_mut().unwrap().next.take();
}
} else {
cur = cur.next.as_mut().unwrap();
}
}
return dummy.unwrap().next;
}
}
go：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return nil
}
dummy := &ListNode{0, head}
cur := dummy
for cur.Next != nil && cur.Next.Next != nil {
if cur.Next.Val == cur.Next.Next.Val {
v := cur.Next.Val
for cur.Next != nil && cur.Next.Val == v {
cur.Next = cur.Next.Next
}
} else {
cur = cur.Next
}
}
return dummy.Next
}
c++：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) {
return head;
}
ListNode *dummy = new ListNode(0, head);
ListNode *cur = dummy;
while (cur->next && cur->next->next) {
if (cur->next->val == cur->next->next->val) {
int v = cur->next->val;
while (cur->next && cur->next->val == v) {
cur->next = cur->next->next;
}
} else {
cur = cur->next;
}
}
return dummy->next;
}
};
python：
# 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: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
dummy = ListNode(0, head)
cur = dummy
while cur.next and cur.next.next:
if cur.next.val == cur.next.next.val:
v = cur.next.val
while cur.next and cur.next.val == v:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
java：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
final ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
int v = cur.next.val;
while (cur.next != null && cur.next.val == v) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~
