LeetCode：移除重复节点-java实现

青旅半醒 2023-02-20 12:13 47阅读 0赞

### 题目描述 ###

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

示例1:

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

输入：\[1, 1, 1, 1, 2\]  
输出：\[1, 2\]  
提示：

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

### 实现代码 ###

package com.chenbin.demo;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.HashSet;
    import java.util.Set;
    
    public class Day0626 { 
        public static ListNode removeDuplicateNodes(ListNode head) { 
    
            if (head == null || head.next == null) { 
                return head;
            }
            Set<Integer> set = new HashSet<>();
            ListNode p = head;
            set.add(p.val);
            while (p.next != null ) { 
                if (set.contains(p.next.val)) { 
                    p.next = p.next.next;
                }else { 
                    set.add(p.next.val);
                    p = p.next;
                }
            }
            return head;
        }
    
        public static int[] stringToIntegerArray(String input) { 
            input = input.trim();
            input = input.substring(1, input.length() - 1);
            if (input.length() == 0) { 
                return new int[0];
            }
    
            String[] parts = input.split(",");
            int[] output = new int[parts.length];
            for (int index = 0; index < parts.length; index++) { 
                String part = parts[index].trim();
                output[index] = Integer.parseInt(part);
            }
            return output;
        }
    
        public static ListNode stringToListNode(String input) { 
            // Generate array from the input
            int[] nodeValues = stringToIntegerArray(input);
    
            // Now convert that list into linked list
            ListNode dummyRoot = new ListNode(0);
            ListNode ptr = dummyRoot;
            for (int item : nodeValues) { 
                ptr.next = new ListNode(item);
                ptr = ptr.next;
            }
            return dummyRoot.next;
        }
    
        public static String listNodeToString(ListNode node) { 
            if (node == null) { 
                return "[]";
            }
    
            String result = "";
            while (node != null) { 
                result += Integer.toString(node.val) + ", ";
                node = node.next;
            }
            return "[" + result.substring(0, result.length() - 2) + "]";
        }
    
        public static void main(String[] args) throws IOException { 
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            String line;
            while ((line = in.readLine()) != null) { 
                ListNode head = stringToListNode(line);
    
                ListNode ret = removeDuplicateNodes(head);
    
                String out = listNodeToString(ret);
    
                System.out.print(out);
            }
        }
    
    }
    
    class ListNode { 
        int val;
        ListNode next;
    
        ListNode(int x) { 
            val = x;
        }
    }

### 解题思路： ###

关键词：单链表、**java对象赋值和引用**、链表删除节点。  
整体思路：创建一个HashSet实例，从头节点开始遍历所有节点，遍历过程中如果HashSet中包括该节点的值，则判断下一个节点的值，否则将该节点的值添加到HashSet中。  
明确5点：1 ：每个节点都是一个对象，有不同的地址。  
2：每个对象之间由next连接。  
3：已知头结点，head。  
4：将HashSet中已存在的节点删除（p.next = p.next.next）  
5: 返回新的头结点。  
实现思路：单链表好比5个单向连接的有色球，颜色有重复，人工要实现这些球颜色不重复，那么从第二个球开始判断，如果和第一个颜色一样，则将第一个球的链子连接到第三个，在从第三个的下一个判断是否重复，以此类推。人工去重的这只“手”就好比程序中对象地址的引用，因此需要实例化一个ListNode p = head； （p在遍历过程中逐一引用节点地址，若节点的值在set中已存在，则修改该节点的next）【判断值从第二个节点开始，修改节点的next从第一个节点开始】。从第一个节点开始所有节点的next都已判断校正过。包括第一个节点。而第一个节点就是head, 因此返回head即可。  
**核心点是ListNode p = head; p的角色和作用。**

参考：java对象的引用以及对象的赋值https://blog.csdn.net/smilelvcha/article/details/81531184