Remove Duplicates from Sorted List II

Medium

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

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

Solution

Two Pointers - prev指向不重复的节点，head则指向最后一个重复节点（或者不重复节点，如果prev.next == head）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode prev = dummy;
        while (head != null && head.next != null) {
            while (head.next != null && head.val == head.next.val) {
                head = head.next;
            } 
            if (prev.next == head) {
                prev = prev.next;
            } else {
                prev.next = head.next;
            }
            head = head.next;
        }
        return dummy.next;
    }
}

From Jiuzhang 一个head指针加一个dummy node搞定：

基本思想：遇到重复节点，就不断删除，非重复节点，就直接前进。

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)
            return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;

        while (head.next != null && head.next.next != null) {
            if (head.next.val == head.next.next.val) {
                int val = head.next.val;
                // keep deleting the duplicated value
                while (head.next != null && head.next.val == val) {
                    head.next = head.next.next;
                }            
            } else {
                head = head.next;
            }
        }

        return dummy.next;
    }
}

用两个指针， 通俗易懂。慢指针永远指着非重复的数， 快指针永远指着最后一个重复的数。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        ListNode fast = head, slow = dummy;
        slow.next = fast;
        while (fast != null){
            while (fast.next != null && (fast.val == fast.next.val)) {
                fast = fast.next;
            }

            if (slow.next != fast) {
                slow.next = fast.next;
            } else {
                slow = slow.next;
            }
            fast = fast.next;
        }
        return dummy.next;
    }
}