移除重复节点

面试题 02.01. 移除重复节点

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

示例1:

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

示例2:

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

提示：

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

进阶：

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

我们可以使用哈希表来存储不重复的结点元素，在遍历过程中只用O(1) 时间就可判断出该结点是否重复。

/**
 * 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;
        }
        ListNode p = head;
        Map<Integer,Integer> map = new HashMap<>();
        //将第一个结点放入 HashMap
        map.put(head.val, 1);
        
        while(p.next != null){
            //判断结点是否重复
            if(!map.containsKey(p.next.val)){
                //不重复，将结点值加入 HashMap
                map.put(p.next.val, 1);
                p = p.next;
            }else{
                //重复，删除下一个结点
                p.next = p.next.next;
            }
        }
        return head;
    }
}

时间复杂度 O(n)，空间复杂度O(n)。

我们也可以直接使用暴力求解，在遍历链表的每个结点时，使用另一个指针，遍历当前结点之后的所有结点，若与当前结点值相同则删除。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        ListNode p = head, q = head;
        while(p != null){
            q = p;
            //删除后续结点中与 p 指向的结点值相同的结点
            while(q.next != null){
                if(q.next.val == p.val){
                    q.next = q.next.next;
                }else{
                    q = q.next;
                }
            }
            p = p.next;
        }
        return head;
    }
}

时间复杂度O(n^2)，空间复杂度O(1)。