【力扣每日一题】力扣82删除排序链表中的重复元素II

发布时间:2024年01月15日

题目来源

力扣82删除排序链表中的重复元素II

题目描述

给定一个已排序的链表的头?head?,?删除原始链表中所有重复数字的节点,只留下不同的数字?。返回?已排序的链表?。

思路分析

1.将遍历到的每一个元素都与上一次加入的元素对比;

2.如果相同,上一次加入的元素删除,并且继续向后找到第一个不同的元素;

2.如果不同,直接将该元素加入筛选队列末尾。

代码实现

java实现

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 头节点
        ListNode result = new ListNode(-101);
        // 已筛选筛选队列末尾指针
        ListNode filteredLast = result;
        // 已筛选队列末尾前驱指针,用于回溯
        ListNode filteredLastfront = result;
        // 未删选队列头指针
        ListNode unfilteredFirst = head;
        while (unfilteredFirst != null) {
            // 如果相同,回溯已筛选队列,未筛选队列相同元素抛弃
            if (filteredLast.val == unfilteredFirst.val) {
                do {
                    unfilteredFirst = unfilteredFirst.next;
                } while (unfilteredFirst != null && unfilteredFirst.val == filteredLast.val);
                filteredLast = filteredLastfront;
                filteredLast.next = null;
            }else {
                // 不相同直接加入
                filteredLastfront = filteredLast;
                filteredLast = filteredLast.next = unfilteredFirst;
                unfilteredFirst = unfilteredFirst.next;
            }
        }
        return result.next;
    }
}

c++实现

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 头节点
        ListNode* result = new ListNode(-101);
        // 已筛选筛选队列末尾指针
        ListNode* filteredLast = result;
        // 已筛选队列末尾前驱指针,用于回溯
        ListNode* filteredLastfront = result;
        // 未删选队列头指针
        ListNode* unfilteredFirst = head;
        while (unfilteredFirst != nullptr) {
            // 如果相同,回溯已筛选队列,未筛选队列相同元素抛弃
            if (filteredLast->val == unfilteredFirst->val) {
                do {
                    unfilteredFirst = unfilteredFirst->next;
                } while (unfilteredFirst != nullptr && unfilteredFirst->val == filteredLast->val);
                filteredLast = filteredLastfront;
                filteredLast->next = nullptr;
            }
            else {
                // 不相同直接加入
                filteredLastfront = filteredLast;
                filteredLast = filteredLast->next = unfilteredFirst;
                unfilteredFirst = unfilteredFirst->next;
            }
        }
        return result->next;
    }
};

文章来源:https://blog.csdn.net/qq_56460466/article/details/135593677
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。