算法---删除排序链表中的重复元素 II

1 题目

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

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

(注: 来自leetcode)

2 解法一

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* deleteDuplicates(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* root = NULL; // root 表示要返回的元素指针, 赋值给第一个唯一元素, 可以通过NULL来做判断是否为第一次赋值
    struct ListNode* pre = NULL; // 上一个唯一元素, 当找到一个唯一元素, 需要与上一个唯一元素连接起来
    while(cur) {
        bool cur_delete_flag = false; // 表示当前该元素是否该删除
        while (cur && cur->next && cur->val == cur->next->val) { // 循环出所有相等的元素
            cur = cur->next;
            cur_delete_flag = true;
        }

        if (!cur_delete_flag) {
            if (root == NULL) { // 表示第一个唯一的元素
                root = cur;
            }
            if (pre) {
                pre->next = cur; // 与上一个唯一元素连接起来
            }
            pre = cur;
        } else {
            if (pre) {
                pre->next = cur->next; // 舍弃掉相同的元素
            }
        }
        cur = cur->next;
    }

    return root;
}

3 解法二

解法2加了一个头节点, 让行为相对统一

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {  // 假如是空或者只有一个元素就不用比较了
        return head;
    }

    struct ListNode tmp; // 作为头节点来表示第一个唯一元素
    struct ListNode* pre = &tmp; // 表示上一个唯一元素
    pre->next = head;
    struct ListNode* iter = pre->next->next;
    bool mark = false;
    while(iter != NULL){
        if (pre && pre->next->val == iter->val) {// 比较的是上一个唯一的元素的后面元素是否相等
            pre->next->next = iter->next; // 如果相等删除当前元素, 但不能删除pre->next, 留作后面的比较
            mark = true;
        } else { // 如果不相等
            if (mark) { // 说明pre->next相同过, pre不能改变, 但是要删除pre->next
                pre->next = iter;
                mark = false;
            } else { // 说明pre->next是唯一的元素, 要更新pre以及
                pre = pre->next;
            }
        }
        iter = iter->next;
    }

    if (mark) {  // 表示上pre->next相同过, 需要删除
        pre->next = NULL;
    }

    return tmp.next;
}

解法3

解法3和解法2类似, 只是多加了一层循环来找出与当前元素值不同的元素, 简洁了很多.

struct ListNode* deleteDuplicates(struct ListNode* head){
     if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode tmp;
    struct ListNode* pre = &tmp;
    pre->next = head;
    struct ListNode* cur = pre->next;
    while(cur) {
        while(cur && cur->next && cur->val == cur->next->val){ // 移动cur一直到与cur->next值不同 
            cur = cur->next;
        }

        if (pre->next == cur) { // 表示cur没移动过, 也就是唯一的元素值
            pre = cur;
        } else {
            pre->next = cur->next;
        }

        cur = cur->next;
    }

    return tmp.next;
}