82. Remove Duplicates from Sorted List II

Question

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

Thinking:

• Method 1:
  • 递归
    • 以当前的结点作为当前函数的头。
    • 如果下一个存在并且和当前的不一样，则用下一个进行递归。
    • 如果下一个和当前的是一致的，则一直递归到不一样的结点。

/**
 * 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 temp = head.next;
        if(temp.val != head.val){
            head.next = deleteDuplicates(temp);
            return head;
        }else{
            while(temp != null && temp.val == head.val)
                temp = temp.next;
            return deleteDuplicates(temp);
        }
    }
}

• Method 2:遍历

/**
 * 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) return head;
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = dummy.next;
        while(cur.next != null){
            if(cur.next.val != cur.val){
                if(pre.next == cur)
                    pre = pre.next;
                else
                    pre.next = cur.next;
            }
            cur = cur.next;
        }
        if(pre.next != cur)
            pre.next = cur.next;
        return dummy.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 temp = head.next;
        if(temp.val != head.val){
            head.next = deleteDuplicates(temp);
            return head;
        }else{
            temp = temp.next;
            while(temp != null && temp.val == head.val)
                temp = temp.next;
            return deleteDuplicates(temp);
        }
    }
}

Reference

1. Remove Duplicates from Sorted List II