题目

题目链接
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]

示例2:

 输入：[1, 1, 1, 1, 2]输出：[1, 2]

提示：

1. 链表长度在[0, 20000]范围内。
2. 链表元素在[0, 20000]范围内。

实现思路

思路1：
读完题立刻上手，心想这也太简单了，利用set集合筛选掉重复的数据，然后利用头插法构建新链表。
代码如下：

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public ListNode removeDuplicateNodes(ListNode head) {if (head == null) {return head;}ListNode h = head;ListNode temp = new ListNode(0);ListNode root = temp;HashSet<Integer> hashSet = new HashSet<>();while (h != null) {hashSet.add(h.val);h = h.next;}//头插法 构建新链表for (int n : hashSet) {ListNode p = new ListNode(n);temp.next = p;temp = p;}return root.next;}
}

结果出错了，我忘记hashset是无序的，遍历输出的数据是升序排列。所以gg，值对不上。
换个思路。

思路2：
还是利用hashset，循环遍历链表如果hashset中存在下个节点的val则删除下一个节点。否则往下继续遍历，就可以去重了。

代码如下：

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public ListNode removeDuplicateNodes(ListNode head) {if (head == null) {return head;}HashSet<Integer> hashSet = new HashSet<>();ListNode p = head;//头结点的值加入hashset中hashSet.add(p.val);//直到链表遍历结束while (p.next != null) {//如果hashset中不存在next节点的val值就向下移动指向next节点    如果存在next节点的val值就删除此节点也就是修改next的指向给next的nextif (!hashSet.add(p.next.val)) {p.next = p.next.next;} else {p = p.next;}}return head;}
}