首页 算法 02链表

# 题目

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

示例 1：

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

示例 2：

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

tips:

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

# 解法一：HashSet

用 hashset 缓存已经遍历过的结点，在每次拼接下一个节点时，去判读是否已经遍历过这个数字，如果遍历过就跳过，如果没有就拼接在 res 链表上。

/**
 * 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;
        HashSet<Integer> hash = new HashSet<Integer>();
        ListNode pos = head;
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        while(pos !=null){
            if(!hash.contains(pos.val)){
                 hash.add(pos.val);
                 ListNode node = new ListNode(pos.val);
                 cur.next = node;
                 cur = cur.next;
            }
           
            pos = pos.next;
        }
        return res.next;
    }
}
/********************* 稍微改进 ************************************/
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if(head == null) return null;
        HashSet<Integer> hash = new HashSet<Integer>();
        ListNode pos = head;
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        while(pos !=null){
            if(!hash.contains(pos.val)){
                 hash.add(pos.val);
                // ListNode node = new ListNode(pos.val);
                ListNode node = pos;
                 cur.next = node;
                 cur = cur.next;
            }
           
            pos = pos.next;
        }
        cur.next = null;
        return res.next;
    }
}
/********************* 官方题解 ************************************/
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {
            return head;
        }
        Set<Integer> occurred = new HashSet<Integer>();
        occurred.add(head.val);
        ListNode pos = head;
        // 枚举前驱节点
        while (pos.next != null) {
            // 当前待删除节点
            ListNode cur = pos.next;
            if (occurred.add(cur.val)) {
                pos = pos.next;
            } else {
                pos.next = pos.next.next;
            }
        }
        pos.next = null;
        return head;
    }
}
时间复杂度： O (n)，遍历链表一次
空间复杂度：O(N)
# 解法二：进阶
考虑题目描述中的「进阶」部分，是否存在一种不使用临时缓冲区（也就是方法一中的哈希表）的方法呢？
不幸的是，在保证方法一时间复杂度 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 ob = head;
        while (ob != null) {
            ListNode oc = ob;
            while (oc.next != null) {
                if (oc.next.val == ob.val) {
                    oc.next = oc.next.next;
                } else {
                    oc = oc.next;
                }
            }
            ob = ob.next;
        }
        return head;
    }
}
时间复杂度： 其中 O (N2) 其中 N 是给定链表中节点的数目。
空间复杂度： O(1).