AcWing 29. 删除链表中重复的节点

题目

在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。

数据范围

链表中节点 val 值取值范围 。
链表长度 。

样例1

输入：1->2->3->3->4->4->5

输出：1->2->5

样例2

输入：1->1->1->2->3

输出：2->3

题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        auto *root = new ListNode(-1);
        // 根节点也会出现重复
        root -> next = head;
        auto *t = root;
        while (t -> next)
        {
            auto *p = t -> next -> next;
            while(p && t -> next -> val == p -> val) p = p -> next;

            // 如果不是重复，则p会越1位，继续迭代
            if (t -> next -> next == p) t = t -> next;
            else t -> next = p;
        }
        return root -> next;
    }
};