LeetCode_LinkedList_82. Remove Duplicates from Sorted List II 删除排序链表中的重复元素 II（C++）

目录

​​一，题目描述​​

​​英文描述​​

​​中文描述​​

​​二，解题思路​​

​​三，AC代码​​

​​C++​​

​​四，解题过程​​

​​第一博​​

一，题目描述

英文描述

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Example 2:

 

Constraints:

The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.

中文描述

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

示例 1：

示例 2：

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

来源：力扣（LeetCode）
链接：​​​https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii​​ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路

主要思路是：一个指针p指向已处理部分的最后一个节点，另一个指针q负责遍历其余节点，若遇到重复的地方q指针便一直向后遍历，直到q->val != q->next->val，则将重复的一段切掉（p->next = q->next）。

但是一个细节比较难搞，就是怎么移动p指针。

这里借用了一个布尔变量flag，当flag为true时，表明q指针遍历的节点属于重复的一段，那么当q->val != q->next->val时，便可以p->next = q->next，截断这重复的部分。

当flag为false时，表明q指针遍历的节点无重复，p移到q的位置即可。

三，AC代码

C++

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* h = new ListNode;
        h->next = head;
        ListNode* p = h, * q = head;
        // 标记q指针遍历的节点是否存在重复
        bool flag = false;
        while (q->next != nullptr) {
            if (q->val == q->next->val) {
                flag = true;
                q = q->next;
            } else {
                if (flag) p->next = q->next;
                else p = q;

                q = q->next;
                flag = false;
            }
        }
        if (flag) p->next = q->next;
        return h->next;
    }
};

四，解题过程

第一博

终于。。。这一题看似平淡无奇，但细节部分想不明白还是非常头疼的。