"Coding Interview Guide" -- 删除无序单链表中值重复出现的节点

【题目】

　　给定一个无序单链表的头节点head，删除其中值重复出现的节点

　　例如，1->2->3->3->4->4->2->1->1->null，删除值重复的节点之后为1->2->3->4->null

【要求】

　　实现两种方法：

　　1. 如果链表长度为N，时间复杂度达到O(N)

　　2. 空间复杂度为O(1)

【分析】

　　链表是一种逻辑有序，储存位置无序且可非连续的数据结构，链表是线性表的一种，它有0个或多个节点组成，除了第一个节点外每个节点都一个直接前驱节点，除了最后一个节点外，每一个节点都有一个直接后继节点。节点中不仅存储着该节点自身的数据信息还存储该节点的前驱后继节点的存储位置信息。

　　对于方法1，HashSet是一种无序集合，该集合不允许有重复元素。可以通过使用HashSet来判断元素是否重复，如果当前访问的链表节点不在HashSet中，则将该节点放进集合中，如果当前访问的链表节点与当前HashSet中的某个元素相同，则删除链表中的该节点。整个过程只需遍历一次链表，所以时间复杂度为O(N)，因为借助了HashSet，所以空间复杂度为O(N)

　 import java.util.HashSet;　　

 1 public void removeRepeat1(Node head)
 2 {
 3     if(head == null) { return; }
 4 
 5     HashSet<Integer> set = new HashSet<>();
 6     Node pre = head;
 7     Node cur = head.next;
 8 
 9     set.add(head.value);
10     while(cur != null)
11     {
12         if(set.contains(cur.value))   
13         {
14             pre.next = cur.next;      // 删除重复节点
15     　　}
16     　　else
17     　　{
18         　　set.add(cur.value);
19         　　pre = cur;
20     　　}
21     　　cur = cur.next;
22     }
23 }

　　方法2要求额外空间复杂度为O(1)，表示不能使用额外的数据结构，所以可以对链表中的每一个元素，都访问一次链表，如果有重复值则删除，因为对于每一个元素都要遍历一个链表查看有没有重复值，所以时间复杂度为O(N^2)

 1 public void removeRepeat2(Node head)
 2 {
 3     if(head == null) { return; }
 4 
 5     Node pre = null;
 6     Node cur = head;
 7     Node next = null;
 8 
 9     while(cur != null)
10     {
11     　　pre = cur;
12     　　next = cur.next;
13     　　while(next != null)           // 对每一个元素都遍历一次链表
14     　　{
15             if(next.value == cur.value)
16         　　{
17             　　pre.next = next.next;   // 删除重复值
18         　　}
19         　　else
20         　　{
21         　　　　pre = next;
22         　　}
23         　　next = next.next;
24     　　}
25     　　cur = cur.next;
26     }
27 }

来源：左程云老师《程序员代码面试指南》