0%

leetcode每日一题-移除重复节点

Posted on Edited on In ,

移除重复节点

image1

链表结构如下

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode(int x) { val = x; }
7
 * }
8
 */

方法一：哈希表

对给定的链表进行一次遍历，并用一个哈希集合(HashSet)来存储所有出现过的节点。在遍历过程中，如果节点的值已经在集合中出现过，就移除该节点。这里有一个需要注意的地方，在移除节点的过程中，我们本质上是把该节点的前驱节点和后继节点相连，但根据链表节点的结构来看，我们无法得到节点的前驱节点，因此我们把枚举对象由当前节点改为前驱节点u，那么当前节点就为u.next，后继节点就为u.next.next，ac代码如下。

1
class Solution {
2
    public ListNode removeDuplicateNodes(ListNode head) {
3
        if(head == null){
4
            return null;
5
        }
6
        ListNode node = head;
7
        Set<Integer> set = new HashSet<Integer>();
8
        set.add(node.val);
9
        //枚举前驱节点
10
        while(node.next != null){
11
            //移除重复节点
12
            if(set.contains(node.next.val)){
13
                if(node.next.next == null){
14
                    node.next = null;
15
                }else{
16
                    node.next = node.next.next;
17
                    continue;
18
                }
19
            }else{
20
              	//向集合中添加未出现过的节点，并向后移动前驱节点
21
                set.add(node.next.val);
22
                node = node.next;
23
            }
24
        }
25
        return head;
26
    }
27
}

复杂度分析：

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

方法二：双重循环

题目有个进阶的要求，即不允许使用临时缓冲区，那么只能用时间换空间。具体就是第一重循环枚举待保留的节点，第二重循环就从该节点开始，到链表的末尾结束，将所有与保留节点相同的节点全部移除。

1
class Solution {
2
    public ListNode removeDuplicateNodes(ListNode head) {
3
        ListNode ob = head;
4
        while (ob != null) {
5
            ListNode oc = ob;
6
            while (oc.next != null) {
7
                if (oc.next.val == ob.val) {
8
                    oc.next = oc.next.next;
9
                } else {
10
                    oc = oc.next;
11
                }
12
            }
13
            ob = ob.next;
14
        }
15
        return head;
16
    }
17
}

复杂度分析

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