83. 删除排序链表中的重复元素：
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
样例 1：
输入：
head = [1,1,2]
输出：
[1,2]
样例 2：
输入：
head = [1,1,2,3,3]
输出：
[1,2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
分析：
- 面对这道算法题目，二当家的再次陷入了沉思。
- 本来要删除重复元素，需要两次遍历，或者额外空间的数据结构，比如映射表。
- 但是题目中说是排序的，也就是说，相同的元素会挨在一起。
- 如果是数组，那我们应该是轮训遍历，判断每个元素是否和前一个元素相同。
- 但是题目中是排序链表，单向链表的特点是只能从前向后遍历，所以我们要判断的是当前元素和下一个元素是否相同，如果相同就删除下一个元素。
- 要注意的是判断链表的结束，链表是没法直接知道长度的，需要一直遍历，判断是否到尾，通常是根据下一个节点是否为空来判断是否到达链表尾。
- 另外还需要注意有可能链表没有任何节点，直接就是空，如果直接循环遍历判断下一个节点是否为空就会异常，所以先要做前置检查。
- 每次写rust访问链表都有一些无语，真的有些啰嗦，但又无可奈何，就凭咱内存安全这点，就值了，这段不是真的吐槽，rust很好用，我就是单纯凑凑字数什么的，但是rust的学习曲线是比较高一些。
题解：
rust：
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if head.is_none() {
return head;
}
let mut head = head;
let mut cur = head.as_mut().unwrap();
while cur.next.is_some() {
if cur.val == cur.next.as_ref().unwrap().val {
cur.next = cur.next.as_mut().unwrap().next.take();
} else {
cur = cur.next.as_mut().unwrap();
}
}
return head;
}
}
go：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return nil
}
cur := head
for cur.Next != nil {
if cur.Val == cur.Next.Val {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}
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 *cur = head;
while (cur->next) {
if (cur->val == cur->next->val) {
cur->next = cur->next->next;
} else {
cur = cur->next;
}
}
return head;
}
};
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
cur = head
while cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
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;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~
