Remove Duplicates from Sorted List II

Remove Duplicates from Sorted List II

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/

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

Thoughts

1. 因为head可能被删掉，因此需要dummy

2. 对重复中的第一个的删除，判断条件是它和它后面的值是否相等。

3. 对重复中的最后一个的删除，需要判断它和上个被删的值是否相等，因此还需要个prior

   .

4. 删除后相当于节点自动前移，不需要node = node.next; 反之则需要。

Code

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode d_head(-1);
        ListNode *d = &d_head, *node = d, *prior = NULL;
        d->next = head;
        while (node != NULL && node->next != NULL) {
            auto next = node->next;
            if (prior != NULL && next->val == prior->val || next->next != NULL && next->next->val == next->val) {
                node->next = next->next;
            } else {
                node = next;
            }
            prior = next;
        }
        return d->next;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node = head;
        ListNode prior = dummy;
        int delVal = 0; boolean valid = false;
        while (node != null) {
            if (node.next != null && node.val == node.next.val || node.val == delVal && valid) {
                prior.next = node.next;
                delVal = node.val;
                valid = true;
            } else {
                prior = node;
            }
            node = node.next;
        }
        return dummy.next;
    }
}

Analysis

TC: O(n)