BM16 删除有序链表中重复的元素-II

题目描述

描述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.

数据范围：链表长度0≤n≤10000，链表中的值满足∣val∣≤1000
要求：空间复杂度O(n)，时间复杂度O(n)
进阶：空间复杂度 O(1)，时间复杂度O(n)

示例1

输入：
{1,2,2}
返回值：
{1}

示例2

输入：
{}
返回值：
{}

解题思路

解法1 Treemap

1.使用Treemap统计每个数字出现的次数
2.遍历map，找出其中出现一次的数字，然后构造新的Node节点，返回即可

解法2 空间复杂度为O（1）的解法

1.使用一个哑结点，将哑结点与head串联
2.pre节点指向哑结点，cur节点指向头节点，开始遍历
3.解答此题的关键在于，找到不重复的节点，然后将pre.next指向这个节点即可

实践代码

解法 1 代码

import java.util.*;
import java.util.Map.Entry;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head
     *            ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        TreeMap<Integer, Integer> map = new TreeMap<>();
        while (head != null) {
            map.put(head.val, map.getOrDefault(head.val, 0) + 1);
            head = head.next;
        }

        ListNode temp = new ListNode(-1);
        head = temp;
        Iterator<Entry<Integer, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Entry<Integer, Integer> entry = iterator.next();
            if (entry.getValue() == 1) {
                temp.next = new ListNode(entry.getKey());
                temp = temp.next;
            }
        }
        
        return head.next;
    }
}

解法2 代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head
     *            ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dump = new ListNode(-1);
        dump.next = head;
        ListNode pre = dump;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                ListNode temp = cur.next;
                while (temp != null && temp.val == cur.val) {
                    temp = temp.next;
                }
                pre.next = temp;
                cur = temp;
            } else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        return dump.next;
    }
}