LeetCode-82. 删除排序链表中的重复元素 II-Java-medium

题目链接

法一（迭代）

    /**
     * 迭代（引入虚拟头节点）
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0, head); // 构建虚拟头节点，方便操作
        ListNode pre = dummy, cur = head, next = head.next;
        while (cur != null && next != null) {
            if (next.val != cur.val) {
                pre = pre.next;
            }
            while (next != null && next.val == cur.val) {
                next = next.next;
            }
            pre.next = next;
            cur = next;
            if (next != null) {
                next = next.next;
            }
        }
        return dummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

法二（递归）

    /**
     * 递归
     * 1. 情况一
     *      1 --> 1 --> 1 --> 2 --> 3
     *      head  next
     *   （1）需要移动next直到出现与当前head.value不相等的情况（含null）
     *   （2）此时的head已经不能要了，因为head已经是重复的节点
     * 2. 情况二
     *      1 --> 2 --> 3
     *     head  next
     *    此时递归返回的节点就作为head的子节点
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates_2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        if (head.val == next.val) { // 情况一
            while (next != null && head.val == next.val) {
                next = next.next;
            }
            head = deleteDuplicates_2(next);
        } else { // 情况二
            head.next = deleteDuplicates_2(next);
        }
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

本地测试

        /**
         * 82. 删除排序链表中的重复元素 II
         */
        lay.showTitle(82);
        Solution82 sol82 = new Solution82();
        int[] nums82 = new int[]{1, 1, 1, 2, 3};
        ListNode head82_1 = new ListNode();
        head82_1 = listOpt.creatListByArray(head82_1, nums82);
        listOpt.showList(head82_1);
        head82_1 = sol82.deleteDuplicates(head82_1.next);
        listOpt.showNoHeadList(head82_1);
        ListNode head82_2 = new ListNode();
        head82_2 = listOpt.creatListByArray(head82_2, nums82);
        listOpt.showList(head82_2);
        head82_2 = sol82.deleteDuplicates_2(head82_2.next);
        listOpt.showNoHeadList(head82_2);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16