面试题 02.01. 移除重复节点

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

示例1:

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

示例2:

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

提示：

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

进阶：

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

解题思路：

显然如果没有进阶条件限制的话，这道题是非常简单的，创建一个set用来存放不重复的节点。然后遍历链表，每次都在set中检查一下是否包含当前节点，如果不包含，就添加到set中，如果包含，则从链表中移除当前节点。比较简单，懒得写代码实现了，直接上进阶吧。

进阶条件的限制其实也不难，不适用缓冲区的话也就是说不能使用set了。我们先遍历一次链表得到最大值和最小值，然后从i=最小值开始遍历，每当链表中有节点的值等于i时，如果未出现过，那么将重复标志置为true，否则删掉当前节点，一直遍历到i=最大值为止。
注意在链表删除节点时，要保留当前节点的前一个节点。并且删除节点以后，当前节点后移，而前置节点是不用移动的。

代码实现如下：

public class RemoveDuplicateNodesLeetCode {

    public class ListNode {
        int val;
        ListNode next;

        public ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        RemoveDuplicateNodesLeetCode cls = new RemoveDuplicateNodesLeetCode();
        int[] arr = { 1, 2, 3, 3, 2, 1 };
        ListNode head = null;
        ListNode beforeNode = head;
        for (int i = 0; i < arr.length; i++) {
            ListNode newNode = cls.new ListNode(arr[i]);
            if (null == head) {
                head = newNode;
                continue;
            }
            beforeNode.next = newNode;
            beforeNode = newNode;
        }
    }

    public ListNode removeDuplicateNodes(ListNode head) {
        ListNode curNode = head;
        int max = 0;
        int min = 100000;
        while (curNode != null) {
            if (curNode.val > max) {
                max = curNode.val;
            }
            if (curNode.val < min) {
                min = curNode.val;
            }
            curNode = curNode.next;
        }
        for (int i = min; i <= max; i++) {
            curNode = head.next;
            ListNode beforeNode = head;
            boolean exits = beforeNode.val == i;
            while (curNode != null) {
                boolean remove = false;
                if (curNode.val == i) {
                    if (exits) {
                        beforeNode.next = curNode.next;
                        remove = true;
                    } else {
                        exits = true;
                    }
                }
                curNode = curNode.next;
                if (!remove) {
                    beforeNode = beforeNode.next;
                }
            }
        }

        return head;

    }

}