算法leetcode｜83. 删除排序链表中的重复元素（rust重拳出击）

文章目录

83. 删除排序链表中的重复元素：
- 样例 1：
- 样例 2：
- 提示：
分析：
题解：
- rust：
- go：
- c++：
- python：
- java：

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 := headfor 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 headcur = headwhile cur.next:if cur.val == cur.next.val:cur.next = cur.next.nextelse:cur = cur.nextreturn 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;}
}