1. 题目

input: 一个无序的、有重复元素的链表（Linked List）

其实顺序在这里并不重要，可以有序也可以无序，lcci那题是无序的，leetcode官方题库83题是有序的，解法一样。

output: 只保留一个重复元素的链表

PS: 不能用单纯的数组来解题，因为题目指明了是链表。

（无序）

• https://leetcode-cn.com/problems/remove-duplicate-node-lcci/

（有序）

• https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

• https://leetcode.com/problems/remove-duplicates-from-sorted-list/

2. 思路

思路 1 - 用 Set / HashSet

1. 新建一个缓冲区，用来记录已经遇到过的node value；
2. 第一个 node 存入缓冲区，假如有 next，就去看 next value；
3. 如果 next value 和缓冲区重合，next 指针就指向再后面的node value（等于跳过重复的node）；
4. 重复第三步，直到 next 指向 null，也就是遍历结束；
5. 返回 Linked List；

实现 1

首先判断这个Linked List 的长度，假如<=1，直接返回；

否则把第一个node作为current node，第二个node作为next node，开始遍历，当 next node 为空时遍历结束（已经达到终点）：

1. 判断 next node value 是否已经存在于 uniqueVals，假如不存在，就把这个 value 存进去，然后两个指针都向后移动一位；
2. 假如已经存在，current node 需要跳过 next node，指向后面一个 node， next node 也要后移一位
   • 但是！！！假如 next node 就是最后一个 node 呢？current node 会直接指向 null，遍历结束，提前跳出循环

这里比较 tricky 的地方在于 head 到底是什么时候发生改变的？

• 因为 current node 是 head 的一个指针，所以当 current node 发生变化时，head 也会变化；
• currentNode.next = nextNode.next; 这行代码会改变原本 linked list 的结构，跳过重复的元素；

// Definition for singly-linked list.
 public class ListNode {
      public int val;
      public ListNode next;
      public ListNode(int x) { val = x; }
  }

public class Solution
{
	public ListNode RemoveDuplicateNodes(ListNode head)
	{
		if (head == null || head.next == null) return head;
		var uniqueVals = new HashSet<int>();
		uniqueVals.Add(head.val);
		var currentNode = head;
		var nextNode = head.next;
		while (nextNode != null)
		{
			if (!uniqueVals.Contains(nextNode.val)){
				uniqueVals.Add(nextNode.val);
				currentNode = nextNode;
				nextNode = currentNode.next;
			}
			else {
			    currentNode.next = nextNode.next;
				if(currentNode.next == null) break;
				nextNode = currentNode.next;
			}
		}
		return head;
	}
}

复杂度

时间复杂度：O(n) - 遍历一次

空间复杂度：O(n)

思路 2 - 不用辅助 set 来记录元素

大致的思路是两个while loop，通过牺牲时间复杂度O(n^2)来达到空间复杂度 O(1)。

内循环先行（快指针），跟外循环（慢指针）的值进行比较。

假如相同，快指针跳过重复元素，前进两格；假如不同，快指针前进一格，直到快指针为 null 结束此次内循环。

快指针内循环结束之后，慢指针前进一格，快指针回归到慢指针的位置，继续开始内循环。

直到慢指针为 null 截止外循环。

实现 2

public ListNode RemoveDuplicateNodes2(ListNode head) {
	if (head == null || head.next == null) return head;
	var slow = head;
	while (slow != null)
	{
		var quick = slow;
		while (quick.next != null)
		{
			if (quick.next.val == slow.val){
				quick.next = quick.next.next;
			}
			else{
				quick = quick.next;
			}
		}
		slow = slow.next;
	}
	return head;
}

复杂度

时间复杂度：O(n^2) - 两个loop

空间复杂度：O(1) - 没有使用额外空间

结语

欢迎大家分享更好的解法~