面试题 02.01. 移除重复节点

怼烎@ 2023-02-20 07:20 99阅读 0赞

# 题目来源 #

[面试题 02.01. 移除重复节点][02.01.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## set ##

使用set或者hash表，头插法

*  遍历链表，如果链表中的值出现过，直接进入下一个节点
 *  如果当前节点值没有出现过，加入set、使用当前节点值创建一个节点，挂载到新链表上

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public static ListNode removeDuplicateNodes(ListNode head) {
        
            Set<Integer> set = new HashSet<>();
            ListNode pre = new ListNode(-1);
            ListNode cur = pre;
            while (head != null){
        
                if (!set.contains(head.val)){
        
                    cur.next = new ListNode(head.val);
                    cur = cur.next;
                    set.add(head.val);
                }
                head = head.next;
                
            }
    
    
            return pre.next;
        }
    }

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

## 不使用临时缓冲区 ##

本来想使用暴力的，但是暴力可以优化

**冒泡排序的思想：** 渐渐扩大不重复的区域

/**
     * 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 fisrt = head;
            while (fisrt != null){
        
                ListNode second = fisrt; // second初始时一定和first相等，之和就一定不相等了
                // second左边的区域一定和first的值不相等
                while (second.next != null){
          // 如果second右边还有区域没有比较
                    if (second.next.val == fisrt.val){
         // 那么比较second为比较区的最左边的值是否与first.val是否相等
                        second.next = second.next.next;  // 如果相等，干掉这个节点
                    }else {
        
                        second = second.next; // 如果不相等，扩大不重复区域
                    }
                }
                fisrt = fisrt.next;
            }
    
    
            return head;
        }
    
    }

疑问：是否可以梳子排序优化  
![在这里插入图片描述][20200624164759446.png]

[02.01.]: https://leetcode-cn.com/problems/remove-duplicate-node-lcci/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200624164840886.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200624163038806.png]: https://img-blog.csdnimg.cn/20200624163038806.png
[20200624164759446.png]: https://img-blog.csdnimg.cn/20200624164759446.png