82. Remove Duplicates from Sorted List II 「删除排序链表中的重复元素 II」

2020年04月20日 66点热度 2人点赞 0条评论

给定一个排序链表,删除所有重复的元素,只留下不存在重复的元素。同时返回的链表也要求是排序的。

例一:
输入: 1->2->3->3->4->4->5
输出: 1->2->5

例二:
输入: 1->1->1->2->3
输出: 2->3

/*
 * 82. Remove Duplicates from Sorted List II
 * https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
 * https://realneo.me/82-remove-duplicates-from-sorted-list-ii/
 */

public class DeleteDuplicatesII {
    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode node = head;
        node.next = new ListNode(1);
        node = node.next;
        node.next = new ListNode(1);
        node = node.next;
        node.next = new ListNode(1);
        node = node.next;
        node.next = new ListNode(2);
        node = node.next;
        node.next = new ListNode(3);

        DeleteDuplicatesII solution = new DeleteDuplicatesII();
        node = solution.deleteDuplicates(head);
        solution.print(node);
    }

    private void print(ListNode node) {
        for (; node != null; node = node.next) {
            System.out.print(node.val);
            System.out.print("->");
        }
        System.out.println("null");
    }

    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode(0), node =  dummyHead;
        dummyHead.next = head;
        boolean remove = false;
        while (node.next != null && node.next.next != null) {
            if (node.next.val == node.next.next.val) {
                node.next =  node.next.next;
                remove = true;
            } else if (remove) {
                node.next = node.next.next;
                remove = false;
            } else {
                node = node.next;
            }
        }
        if (remove) {
            node.next = null;
        }

        return dummyHead.next;
    }
}

Neo

与卿再世相逢日,玉树临风一少年。

文章评论