【剑指 offer】删除链表中重复的结点

1、题目描述

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

样例1

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

样例2

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

2、问题描述：

3、问题关键：

• 注意这题是将重复的结点全部删除，故可能删除头结点，需要建立虚拟头结点。

4、C++代码：

/**
 * 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 *pre = dummy;
        while(pre->next) {
            ListNode *cur = pre->next;
            while(cur && pre->next->val == cur->val) //pre指向的是要比较的元素的前一个位置。如果后面不重复后移动一个，否则
                cur = cur->next;
            if (pre->next->next == cur) pre = pre->next;//如果两个结点不重复，那么它们相差的距离为2。
            else pre->next = cur;
        }
        return dummy->next;
    }
};