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

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

数据范围

链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。

样例1

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

输出：1->2->5

样例2

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

输出：2->3

算法思想

image-20230512213440430

image-20230512213751300

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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) {
        ListNode * dummy = new ListNode(-1);
        dummy -> next = head;
        
        ListNode * p = dummy;
        
        // 保证节点都不为空
        while(p -> next){
            // 被检查的节点
            ListNode * q = p -> next;
            // 由于这是一个已被排序的链表，因此可以通过while循环筛掉一连串的节点
            // 循环跳出的时候 q -> next 就是新的需要被检查的元素，与 q 的值不同
            while(q -> next && q -> val == q -> next -> val) q = q -> next;
            // 如果没有重复的元素，while循环体不会执行，会出现下面这种情况
            // 那么 q 元素是没有重复元素的，就让 p 前进
            // 否则，被筛选了，p 直接跳跃至 q -> next 这个新的需要被筛选元素
            if(p -> next == q) p = p -> next;
            else p -> next = q -> next;
        }
        
        return dummy -> next;
    }
};