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

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}
1
2
3
4

示例2

输入：
{}
返回值：
{}
1
2
3
4

解题思路

解法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;
	}
}
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
31
32
33
34
35
36
37
38
39
40
41
42

解法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;
	}
}
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
31
32
33
34
35
36
37
38
39
40
41