分类
LeetCode

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

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

例一:
输入: 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;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注