力扣---面试题 02.01. 移除重复节点

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

示例 1:

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例 2:

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

链表长度在 [0, 20000] 范围内。
链表元素在 [0, 20000] 范围内。
进阶：

如果不得使用临时缓冲区，该怎么解决？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-duplicate-node-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

先写普通的，即用一个Set来存储遍历过的节点值，然后判断节点是否包含在里面，如果是，那么通过next移除下一个节点。

最近递归用的越来越顺手了。直接用递归写的，但写完后发现其实按照我的思路，也许不写成递归会更简洁点。

非进阶递归：

/**
 * 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 null;
        }
        Set<Integer> set = new HashSet<>();
        delete(head, set);
        return head;
    }
    private void delete(ListNode head, Set<Integer> set) {
        if (head == null || head.next == null) {
            return;
        }
        set.add(head.val);
        if (set.contains(head.next.val)) {
            head.next = head.next.next;
            delete(head, set);
        } else {
            delete(head.next, set);
        }
    }
}

不使用额外缓冲区（实际上就是时间换空间，将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 null;
        }
        delete(head);
        return head;
    }
    private void delete(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode node = head;
        // 遍历，然后删除重复的节点。
        while (node.next != null) {
            if (node.next.val == head.val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        delete(head.next);
    }
}