[程序员面试金典][JAVA][第02.01题][移除重复节点][Set][双指针]

深碍√TFBOYSˉ_ 2023-02-20 10:47 29阅读 0赞

#### 【问题描述】\[简单\] ####

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
    
    示例1:
    
     输入：[1, 2, 3, 3, 2, 1]
     输出：[1, 2, 3]
    示例2:
    
     输入：[1, 1, 1, 1, 2]
     输出：[1, 2]
    提示：
    
    链表长度在[0, 20000]范围内。
    链表元素在[0, 20000]范围内。
    进阶：
    
    如果不得使用临时缓冲区，该怎么解决？

#### 【解答思路】 ####

###### 1. Set/哈希集合 ######

对给定的链表进行一次遍历，并用一个哈希集合（HashSet）来存储所有出现过的节点val  
![在这里插入图片描述][2020062611014284.png]

**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200626110213271.png]

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;
        }
    }

**另一种写法**

public ListNode removeDuplicateNodes(ListNode head) { 
            
            if(head == null){ 
                return null;
            }
            Set<Integer> set = new HashSet<>();
            ListNode pre =head;
            ListNode cur = head.next;
            set.add(head.val);
    
            while(cur!=null){ 
                if(set.contains(cur.val) ){ 
                    pre.next = cur.next;// 连接到最后的null
                    cur= cur.next;
                }
                else{ 
                    set.add(cur.val);
                    pre = cur;
                    cur =cur.next;
                }
            }
    
            return head;
        }

###### 2. 两重循环（冒泡排序） 进阶解法 ######

在给定的链表上使用两重循环，其中第一重循环从链表的头节点开始，枚举一个保留的节点，这是因为我们保留的是「最开始出现的节点」。第二重循环从枚举的保留节点开始，到链表的末尾结束，将所有与保留节点相同的节点全部移除。  
第一重循环枚举保留的节点本身，而为了编码方便，第二重循环可以枚举待移除节点的前驱节点，方便我们对节点进行移除。这样一来，我们使用「时间换空间」的方法，就可以不使用临时缓冲区解决本题了。

**时间换空间**

**时间复杂度：O(N^2) 空间复杂度：O(1)**

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;
        }
    }

#### 【总结】 ####

###### 1.枚举前驱节点 删除节点方便 ######

![在这里插入图片描述][20200626111438630.png]

###### 2.时间空间相互tradeoff ######

###### 3.链表题目画图 切忌心烦意乱 ######

转载链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci/solution/yi-chu-zhong-fu-jie-dian-by-leetcode-solution/

[2020062611014284.png]: https://img-blog.csdnimg.cn/2020062611014284.png
[20200626110213271.png]: https://img-blog.csdnimg.cn/20200626110213271.png
[20200626111438630.png]: https://img-blog.csdnimg.cn/20200626111438630.png