链表Linked List-从未排序的链表中删除重复项Remove duplicates from an unsorted linked list （2）

分手后的思念是犯贱 2023-09-24 18:55 38阅读 0赞

# 问题： #

Given an unsorted list of nodes. The task is to remove duplicates from the list.

Examples:

Input: linked list = 12->11->12->21->41->43->21  
Output: 12->11->21->41->43.  
Explanation: Second occurrence o 12 and 21 is removed

Input: linked list = 12->11->12->21->41->43->21  
Output: 12->11->21->41->43.

# 解题思路： #

## 解题思路1： ##

使用两个循环，外循环用于一个一个地挑选元素，内循环将挑选的元素与其余元素进行比较。

### 代码 ###

class LinkedList {
        
    
        static Node head;
    
        static class Node {
        
    
            int data;
            Node next;
    
            Node(int d)
            {
        
                data = d;
                next = null;
            }
        }
    
        void remove_duplicates(Node head)//删除重复项的函数 未排序的链表
        {
        
            Node ptr1 = null, ptr2 = null;
            ptr1 = head;
    
            /* 一个一个地挑选元素 */
            while (ptr1 != null && ptr1.next != null) {
        
                ptr2 = ptr1;
                while (ptr2.next != null) {
        //将拾取的元素与其余元素进行比较 元素的
    
                    /* 如果重复则删除它 */
                    if (ptr1.data == ptr2.next.data) {
        
                        ptr2.next = ptr2.next.next;
                    } else {
        
                        ptr2 = ptr2.next;
                    }
                }
                ptr1 = ptr1.next;
            }
        }
    
        void printList(Node node)
        {
        
            while (node != null) {
        
                System.out.print(node.data + " ");
                node = node.next;
            }
        }
    
        public static void main(String[] args)
        {
        
            LinkedList list = new LinkedList();
            list.head = new Node(10);
            list.head.next = new Node(12);
            list.head.next.next = new Node(11);
            list.head.next.next.next = new Node(11);
            list.head.next.next.next.next = new Node(12);
            list.head.next.next.next.next.next = new Node(11);
            list.head.next.next.next.next.next.next
                    = new Node(10);
    
            System.out.println(
                    "Linked List before removing duplicates : ");
            list.printList(head);
    
            list.remove_duplicates(head);
            System.out.println("\n");
            System.out.println(
                    "Linked List after removing duplicates : ");
            list.printList(head);
        }
    }

### 运行结果 ###

Linked List before removing duplicates : 
    10 12 11 11 12 11 10 
    
    Linked List after removing duplicates : 
    10 12 11

## 解题思路2： ##

使用哈希从未排序的链表中删除重复项

> 从头到尾遍历链接列表。对于每个新遇到的元素，检查它是否在哈希表中：如果是，我们将其删除；否则将其放入哈希表中。

步骤：

1.  创建一个无序集来跟踪访问过的元素。
2.  从头节点到尾节点遍历链表  
    如果当前节点已经存在于哈希集中。然后删除当前节点。  
    否则移动将节点插入哈希集中并移动到下一个节点。
3.  返回

时间复杂度：平均为 O(N)（假设哈希表访问时间平均为 O(1)）。  
辅助空间：O(N)，因为额外的空间用于存储堆栈中的元素。

### 代码 ###

package com.Amy.leecode;
    
    import java.util.HashSet;
    
    /**
     * @author: Amy
     * @create: 2023-02-15 09:38
     **/
    class LinkedList {
        
    
        static Node head;
    
        static class Node {
        
    
            int data;
            Node next;
    
            Node(int d)
            {
        
                data = d;
                next = null;
            }
        }
    
        void remove_duplicates(Node head)//删除重复项的函数 未排序的链表
        {
        
            HashSet<Integer> set = new HashSet<>();
            Node current = head;
            Node pre=null;
            while(current !=null){
        
                int curval= current.data;
                if (set.contains(curval)) {
        
                    pre.next =current.next;
                }else{
        
                    set.add(curval);
                    pre=current;
                }
                current=current.next;
            }
    
        }
    
        void printList(Node node)
        {
        
            while (node != null) {
        
                System.out.print(node.data + " ");
                node = node.next;
            }
        }
    
        public static void main(String[] args)
        {
        
            LinkedList list = new LinkedList();
            list.head = new Node(10);
            list.head.next = new Node(12);
            list.head.next.next = new Node(11);
            list.head.next.next.next = new Node(11);
            list.head.next.next.next.next = new Node(12);
            list.head.next.next.next.next.next = new Node(11);
            list.head.next.next.next.next.next.next
                    = new Node(10);
    
            System.out.println(
                    "Linked List before removing duplicates : ");
            list.printList(head);
    
            list.remove_duplicates(head);
            System.out.println("\n");
            System.out.println(
                    "Linked List after removing duplicates : ");
            list.printList(head);
        }
    }

### 运行结果 ###

Linked List before removing duplicates : 
    10 12 11 11 12 11 10 
    
    Linked List after removing duplicates : 
    10 12 11