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

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

链表声明：

class ListNode {
    int val;
    ListNode next;
    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

一次遍历

• 每次判断后面一个节点和后两个节点的值是否相同，相同则循环一直把后面的节点删干净，否则直接让游标向后移到。
• dummyHead 解决繁杂的逻辑判断。

public class Solution {

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode dummyHead = new ListNode(0, head);
        ListNode curNode = dummyHead; // curNode start from dummyHead
        // there are at least two node after current node
        while (curNode.next != null && curNode.next.next != null) {
            if (curNode.next.val == curNode.next.next.val) {
                int num = curNode.next.val;
                // delete node which has same num
                while (curNode.next != null && curNode.next.val == num) {
                    curNode.next = curNode.next.next;
                }
            } else {
                curNode = curNode.next;
            }
        }
        return dummyHead.next;
    }

}

递归

• 把 deleteDuplicates(ListNode head) 的功能定义为：删除 head 为首的链表中重复的节点

• 退出条件：if (head == null || head.next == null) return head;

• 遇到当前 head 值跟下一个节点值相同，则让 head跳过这些相同值的节点。然后再递归对后面的元素递归处理

• 不相同，则直接让后面 处理好的链表接到当前 head 上，然后返回。head.next = deleteDuplicates(head.next);

public class Solution {

    // Recursion Solution
    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null) return head;
        if (head.val == head.next.val) {
            // equals jump the same node, then recursion the next node to operate behind listNode
            while (head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            // now Head is the last of the same nodes, so recursion object is head.next
            return deleteDuplicates(head.next);
        } else {
            head.next = deleteDuplicates(head.next);
            return head;
        }
    }

}