83/82-删除链表重复元素

LeetCode 83. Remove Duplicates from Sorted List

LeetCode-83

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1:

Input: head = [1,1,2]
Output: [1,2]

method 1: 递归

如果当前节点和下一个节点重复了，就返回下一个节点
没有重复，就返回当前节点

ListNode* deleteDuplicates(ListNode* head) {
    if (!head) return head;
    head->next = deleteDuplicates(head->next);
    if (head->next && head->val == head->next->val) {
        return head->next;
    }
    return head;
}

method 2: 迭代

如果当前节点的值与下一个节点的值相同，就删掉下一个节点
可能有多个值相同，所以要用循环while

不管相同不相同，cur都要往后走，所以要再嵌套一层while (cur)

ListNode* deleteDuplicates(ListNode* head) {
    ListNode *cur = head;
    while (cur) {
        while (cur->next && cur->next->val == cur->val) {
            cur->next = cur->next->next;
        }
        cur = cur->next;
    }
    return head;
}

---

LeetCode 82. Remove Duplicates from Sorted List II

LeetCode-82

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

method

检查下个节点和下下个节点是否相同，如果相同就记录重复元素，开始删除

ListNode* deleteDuplicates(ListNode* head) {
    if (!head) return head;
    ListNode *dummy = new ListNode(0, head);
    ListNode *cur = dummy;
    while (cur->next && cur->next->next) {
        if (cur->next->val == cur->next->next->val) {
            int x = cur->next->val;
            while (cur->next && cur->next->val == x) {
                cur->next = cur->next->next;
            }
        }
        else {
            cur = cur->next;    // 只有后面两个不重复才能往后走，所以必须else 
        }
    }
    return dummy->next;
}