题目描述：

给定一个已排序的链表的头 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
题目数据保证链表已经按升序 排列

题解：

解题思路：

思路一（模拟）：

1、为了方便对单链表进行删除操作，创建一个dummy结点（哑结点），dummy->head->…->nullptr。
判断一个结点是否需要保留，需要判断其后一个结点和此节点是否相同。

• 若后一个结点和此节点相同则需继续向后判断直到找到一个节点的值和此节点不同的结点，将这些值相同的结点进行删除。
• 若后一个结点和此节点不同，则保留。
• 继续重复上述操作。直到链表结束

例：head = [1,1,1,2,3]
[【1,1】,1,2,3] ，1 和 1值相同则删除所有相邻等于1的结点
[2,3]
2、复杂度分析：
① 时间复杂度：O(N)，N代表链表中结点的个数，只遍历了链表一遍。
② 空间复杂度：O(1)，使用了常数个额外空间。

代码实现

代码实现（思路一（模拟））：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 如果链表为空，直接返回空
        if (head == nullptr) return head;

        // 创建一个虚拟节点，虚拟节点的下一个节点指向原链表的头节点
        // 这样可以简化边界情况的处理，尤其是在删除节点时，防止修改头节点
        ListNode *dummy = new ListNode(0, head);

        // 用于删除节点的指针
        ListNode *deleteNode;
        
        // 当前节点从虚拟节点开始，这样方便处理链表头部的重复节点
        ListNode *curNode = dummy;

        // 遍历链表，直到链表末尾
        while (curNode->next != nullptr && curNode->next->next != nullptr) {
            // 如果当前节点的值与下一个节点的值相等，说明出现重复节点
            if (curNode->next->val == curNode->next->next->val) {
                int x = curNode->next->val;  // 保存重复节点的值

                // 删除所有与当前值相等的节点
                while (curNode->next != nullptr && curNode->next->val == x) {
                    // 保存要删除的节点
                    deleteNode = curNode->next;
                    // 将当前节点的next指向下一个节点，从链表中删除当前节点
                    curNode->next = curNode->next->next;
                    // 释放删除节点的内存
                    delete deleteNode;
                }
            } else {
                // 如果当前节点和下一个节点的值不同，继续向后移动
                curNode = curNode->next;
            }
        }

        // 返回去重后的链表，虚拟节点的下一个节点即为新的头节点
        head = dummy->next;
        // 释放虚拟节点的内存
        delete dummy;

        return head;  // 返回去重后的链表
    }
};

以思路一为例进行调试

#include<iostream>
#include<vector>
using namespace std;

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){}
};

//尾插法创建单链表
ListNode *createList(vector<int> arr){
    ListNode *head=nullptr,*tail=nullptr;
    for (const auto &val : arr){
        if (head==nullptr){
            tail=head=new ListNode(val);
        }else{
            tail->next=new ListNode(val);
            tail=tail->next;
        }
    }
    return head;
}
/** 方法一：模拟
 * 为了方便对单链表进行操作，创建一个dummy结点（哑结点），dummy->head->....->nullptr
 * 判断一个结点是否需要保留，需要判断其后一个结点和此节点是否相同。
 *      若后一个结点和此节点相同则需继续向后判断直到找到一个节点的值和此节点不同的结点，将这些值相同的结点进行删除。
 *      若后一个结点和此节点不同，则保留。
 *      继续重复上述操作。直到链表结束
 * 
 * 例：head = [1,1,1,2,3]
 * [【1,1】,1,2,3] ，1 和 1值相同则删除所有相邻等于1的结点
 * [2,3]
 */

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 如果链表为空，直接返回空
        if (head == nullptr) return head;

        // 创建一个虚拟节点，虚拟节点的下一个节点指向原链表的头节点
        // 这样可以简化边界情况的处理，尤其是在删除节点时，防止修改头节点
        ListNode *dummy = new ListNode(0, head);

        // 用于删除节点的指针
        ListNode *deleteNode;
        
        // 当前节点从虚拟节点开始，这样方便处理链表头部的重复节点
        ListNode *curNode = dummy;

        // 遍历链表，直到链表末尾
        while (curNode->next != nullptr && curNode->next->next != nullptr) {
            // 如果当前节点的值与下一个节点的值相等，说明出现重复节点
            if (curNode->next->val == curNode->next->next->val) {
                int x = curNode->next->val;  // 保存重复节点的值

                // 删除所有与当前值相等的节点
                while (curNode->next != nullptr && curNode->next->val == x) {
                    // 保存要删除的节点
                    deleteNode = curNode->next;
                    // 将当前节点的next指向下一个节点，从链表中删除当前节点
                    curNode->next = curNode->next->next;
                    // 释放删除节点的内存
                    delete deleteNode;
                }
            } else {
                // 如果当前节点和下一个节点的值不同，继续向后移动
                curNode = curNode->next;
            }
        }

        // 返回去重后的链表，虚拟节点的下一个节点即为新的头节点
        head = dummy->next;
        // 释放虚拟节点的内存
        delete dummy;

        return head;  // 返回去重后的链表
    }
};

int main(int argc, char const *argv[])
{
    vector<int> nums={1,2,3,3,4,4,5};
    //创建单链表
    ListNode *head=createList(nums);

    //验证单链表是否创建成功
    // while (head!=nullptr){
    //     cout<<head->val<<" ";
    //     head=head->next;
    // }
    
    return 0;
}

LeetCode 面试经典 150_链表_删除排序链表中的重复元素 II（63_82)原题链接
欢迎大家和我沟通交流(✿◠‿◠)