移除重复节点

发表于 | 分类于 |
字数统计: 554 字 | 阅读时长 ≈ 2 分钟

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

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

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

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

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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<>();
    ListNode cur = head;
    set.add(cur.val);
    while(cur.next != null) {
      if(!set.add(cur.next.val)) {
        cur.next = cur.next.next;
      } else {
        cur = cur.next;
      }
    }
    return head;
  }
}

复杂度分析

  • 时间复杂度：O(N)，其中 N 是给定链表中节点的数目。

  • 空间复杂度：O(N)。在最坏情况下，给定链表中每个节点都不相同，哈希表中需要存储所有的 N 个值。

执行结果：通过

  • 执行用时：5 ms, 在所有 Java 提交中击败了91.45%的用户
  • 内存消耗：39.7 MB, 在所有 Java 提交中击败了59.78%的用户

方法二：两重循环

【以时间换空间】

我们在给定的链表上使用两重循环，其中第一重循环从链表的头节点开始，枚举一个保留的节点，这是因为我们保留的是「最开始出现的节点」。第二重循环从枚举的保留节点开始，到链表的末尾结束，将所有与保留节点相同的节点全部移除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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 prev = head;
    while(prev != null) {
      ListNode cur = prev;
      while(cur.next != null) {
        if(cur.next.val == prev.val) {
          cur.next = cur.next.next;
        } else {
          cur = cur.next;
        }
      }
      prev = prev.next;
    }
    return head;
  }
}

复杂度分析

  • 时间复杂度：O(N^2)，其中 N 是给定链表中节点的数目。
  • 空间复杂度：O(1)。

执行结果：通过

  • 执行用时：392 ms, 在所有 Java 提交中击败了14.27%的用户

  • 内存消耗：39.3 MB, 在所有 Java 提交中击败了79.88%的用户