[链表] LeetCode 82. 删除排序链表中的重复元素 II_leetcod 82

[链表] LeetCode 82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5
1
2

示例 2:

输入: 1->1->1->2->3
输出: 2->3
1
2

首先增加一个头节点，用p指向当前结点，设置两个变量left和right指向p->next，

对比left->val == right->next->val ，如果相等则right指向下一个，直到不等，有两种情况

一：如果没有重复数字left和right将是一个结点，则此时只需向p后移，

二：如果不等则left-right表示的是重复数字的区间，right是重复数字的最后一个结点，则p的下一个结点指向right的下一个节点

特点就是不需要新建结点在添加，只需在原来的链表中切割即可，非常方便

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *p = new ListNode(0);
        p->next = head;
        head = p;
        ListNode *left,*right;
        while(p->next){
            left = p->next;
            right = p->next;
            while(right->next&&left->val == right->next->val)
                right = right->next;
            if(right==left)//无重复数字
                p = p->next;	
            else		   //有重复数字，将区间截断
                p->next = right->next;
        }
        return head->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20