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

文章目录

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 <= Node.val <= 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<Box<ListNode>>// }//// impl ListNode {//   #[inline]//   fn new(val: i32) -> Self {//     ListNode {//       next: None,//       val//     }//   }// }implSolution{pubfndelete_duplicates(head:Option<Box<ListNode>>)->Option<Box<ListNode>>{if head.is_none(){return head;}letmut dummy =Option::Some(Box::new(ListNode::new(0)));
        dummy.as_mut().unwrap().next = head;letmut 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
 * }
 */funcdeleteDuplicates(head *ListNode)*ListNode {if head ==nil{returnnil}

    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) {}
 * };
 */classSolution{public:
    ListNode*deleteDuplicates(ListNode* head){if(!head){return head;}

        ListNode *dummy =newListNode(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 = nextclassSolution:defdeleteDuplicates(self, head: Optional[ListNode])-> Optional[ListNode]:ifnot head:return head

        dummy = ListNode(0, head)

        cur = dummy
        while cur.nextand cur.next.next:if cur.next.val == cur.next.next.val:
                v = cur.next.val
                while cur.nextand cur.next.val == v:
                    cur.next= cur.next.nextelse:
                cur = cur.nextreturn 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; }
 * }
 */classSolution{publicListNodedeleteDuplicates(ListNode head){if(head ==null){returnnull;}finalListNode dummy =newListNode(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/ 博客原创~