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

题目来源

力扣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;
    }
};