题目内容

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

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

示例

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示

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

题解

本题考察双指针算法。具体思考如下：

链表题一般先定义一个虚拟头结点用于指向真实的头结点dummy，方便我们后续操作。

接着，假设有p和q两个指针，固定p移动q，q每次扫描相同的一段，若元素个数多余1个，整段元素删除：p=q->next，然后让q继续扫描。

时间复杂度：整个链表只扫描一遍，所以时间复杂度是 O(n)。

代码

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        //双指针算法
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        auto p = dummy;//指向相同链表段的前一个指针
        while(p -> next){
            auto q = p -> next -> next;
            while(q && (q -> val == p -> next -> val)) q = q -> next;
            if(p -> next -> next == q) 
                //说明下一段只有一个数
                p = p -> next;
            else p -> next = q;
        }
        return dummy -> next;
    }
};