编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:
输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
题意：就是让我们去除单链表中的重复节点，只保留第一个。
思路：递归求解，用一个set存放节点的值，如果这个节点的值没出现过就存放到set中，保留当前节点；如果这个节点的值出现过就舍弃当前节点。
代码：
class Solution01061 { private Set<Integer> set =new HashSet<Integer>(); public ListNode removeDuplicateNodes(ListNode head) { if(head==null) //说明到了链表尾端 return null; if(!set.contains(head.val)){ //这个值第一次出现 set.add(head.val); //set中加入这个值，用于下次判断 //只要这个链表不是空的,那么第一次经过if时的第一个节点就会保存下来,所以只要这个链表不是空的,至少会有一个节点 //这句相当于保留了这个节点,然后往后面挂下一个符合要求的节点 head.next=removeDuplicateNodes(head.next); // 这句就相当于保留了当前节点 return head; }else{ //这个值出现过了 // 不要当前节点,直接对下一个节点验证 return removeDuplicateNodes(head.next); } } }
完整代码（含测试样例）：
package com.Keafmd.day0106; import java.util.HashSet; import java.util.Set; /** * Keafmd * * @ClassName: RemoveDuplicateNode * @Description: 移除重复节点 https://leetcode-cn.com/problems/remove-duplicate-node-lcci/ * @author: 牛哄哄的柯南 * @date: 2021-01-06 19:31 */ public class RemoveDuplicateNode { public static void main(String[] args) { Solution solution = new Solution(); ListNode listNode1 = new ListNode(1); ListNode listNode2 = new ListNode(2); ListNode listNode3 = new ListNode(3); ListNode listNode4 = new ListNode(3); ListNode listNode5 = new ListNode(2); ListNode listNode6 = new ListNode(1); ListNode listNode7 = new ListNode(1); listNode1.next = listNode2; listNode2.next = listNode3; listNode3.next = listNode4; listNode4.next = listNode5; listNode5.next = listNode6; listNode6.next = listNode7; ListNode result = solution.removeDuplicateNodes(listNode1); System.out.println(result.val); System.out.println(result.next.val); } } class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } class Solution { private Set<Integer> set =new HashSet<Integer>(); public ListNode removeDuplicateNodes(ListNode head) { if(head==null) //说明到了链表尾端 return null; if(!set.contains(head.val)){ //这个值第一次出现 set.add(head.val); //set中加入这个值，用于下次判断 //只要这个链表不是空的,那么第一次经过if时的第一个节点就会保存下来,所以只要这个链表不是空的,至少会有一个节点 //这句相当于保留了这个节点,然后往后面挂下一个符合要求的节点 head.next=removeDuplicateNodes(head.next); // 这句就相当于保留了当前节点 return head; }else{ //这个值出现过了 // 不要当前节点,直接对下一个节点验证 return removeDuplicateNodes(head.next); } } }
测试结果：
1 2 Process finished with exit code 0
