从未排序的链表中删除重复项

Question

import java.util.*;
/*
 *  Remove duplicates from an unsorted linked list
 */
public class LinkedListNode {  
    public int data;  
    public LinkedListNode next;  

    public LinkedListNode(int data) {  
        this.data = data;    
    }  
}

public class Task {
    public static void deleteDups(LinkedListNode head){
      Hashtable<Integer, Boolean> table=new Hashtable<Integer, Boolean>();
      LinkedListNode previous=null;
      //nth node is not null
      while(head!=null){
        //have duplicate
            if(table.containsKey(head.data)){
                            //skip duplicate
                previous.next=head.next;
            }else{
            //put the element into hashtable
            table.put(head.data,true);
            //move to the next element
            previous=head;
            }
      //iterate
      head=head.next;
      }
   }
   public static void main (String args[]){
       LinkedList<Integer> list=new LinkedList<Integer>();
       list.addLast(1);
       list.addLast(2);
       list.addLast(3);
       list.addLast(3);
       list.addLast(3);
       list.addLast(4);
       list.addLast(4);
       System.out.println(list);
       LinkedListNode head=new LinkedListNode(list.getFirst());
       Task.deleteDups(head);
       System.out.println(list);
   }
}

结果：[1, 2, 3, 3, 3, 4, 4] [1, 2, 3, 3, 3, 4, 4]

它没有消除重复项。

为什么这种方法行不通？

- Ivan

---

http://stackoverflow.com/questions/9459557/java-remove-duplicates-from-linked-list - user2579943

你没有从 deleteDups 方法中返回新列表。 - Rohit Jain

我建议您在IDE中使用调试器逐步执行代码并理解它。如果您不知道如何使用它，现在学习也不迟。我也建议您不要使用Hashtable，因为它已经是过时类别大约15年了。您应该使用像HashSet这样的集合。 - Peter Lawrey

你的列表并没有连接。虽然你在添加节点，但是由于每个元素都没有设置“next”指针，所以你的函数会立即返回。 - Minh Nguyen

Answer 1

遍历链表，将每个元素添加到哈希表中。当我们发现重复元素时，删除该元素并继续迭代。由于使用的是链表，因此可以在一次遍历中完成所有操作。

以下解决方案需要O(n)时间，n为链表中的元素数。

public static void deleteDups (LinkedListNode n){
  Hashtable table = new Hashtable();
  LinkedListNode previous = null;
  while(n!=null){
      if(table.containsKey(n.data)){
          previous.next = n.next;
      } else {
          table.put(n.data, true);
          previous = n;
      }
      n = n.next;
  }
}

- user3000711

---

为什么你使用 HashMap 而不是 HashSet？这里键的值是不必要的。虽然 HashSet 是由 HashMap 支持的，但使用它对设计没有任何意义。 - wayfare

这里应该使用适当的数据结构是 HashSet，而不是 map，更不是线程安全的 map。 - CaptainHastings

这里使用previous是用来干什么的？为什么下面这样的代码行不通？ public static void deleteDups (LinkedListNode n){ HashSet set = new HashSet(); while(n!=null){ if(set.containsKey(n.data)){ n=n.next } else { table.put(n.data, true); n=n.next; } } } - gotit

Answer 2

1. The solution you have provided does not modify the original list.
2. To modify the original list and remove duplicates, we can iterate with two pointers. Current: which iterates through LinkedList, and runner which checks all subsequent nodes for duplicates.

3. The code below runs in O(1) space but O(N square) time.

   public void deleteDups(LinkedListNode head){

   if(head == null)
       return;
   
   LinkedListNode currentNode = head;       
   while(currentNode!=null){
       LinkedListNode runner = currentNode;
       while(runner.next!=null){
           if(runner.next.data == currentNode.data)
               runner.next = runner.next.next;
           else
               runner = runner.next;
       }
       currentNode = currentNode.next;
   }
   

   }

参考资料：Gayle Laakmann McDowell

- Rambo7

---

Maxime：如果您认为这个解决方案正确，请点赞支持一下吧 :) - Rambo7

这不是最优解，所以它不是正确答案。 - Didac Perez Parera

我从未争论过我的解决方案是最优的（已在解决方案中解释）。仅仅因为解决方案不是最优的，并不意味着解决方案不正确。 - Rambo7

这个相同的解决方案在《程序员面试金典》一书中也有提到。 - Rushi

Rambo7，我认为你的解决方案在重复项是列表中的最后一个元素时将无法工作，因为 runner.next！= null 检查将失败。我没有测试过它，但可以尝试像这样的东西：//0 1 2 3 4 1 - user1529412

Answer 3

以下是两种在Java中实现的方式。上述方法的时间复杂度为O(n)，但需要额外的空间。而第二个版本的时间复杂度为O(n^2)，但不需要额外的空间。

import java.util.Hashtable;

public class LinkedList {
LinkedListNode head;

public static void main(String args[]){
    LinkedList list = new LinkedList();
    list.addNode(1);
    list.addNode(1);
    list.addNode(1);
    list.addNode(2);
    list.addNode(3);
    list.addNode(2);

    list.print();
    list.deleteDupsNoStorage(list.head);
    System.out.println();
    list.print();
}

public void print(){
    LinkedListNode n = head;
    while(n!=null){
        System.out.print(n.data +" ");
        n = n.next;
    }
}

public void deleteDups(LinkedListNode n){
    Hashtable<Integer, Boolean> table = new Hashtable<Integer, Boolean>();
    LinkedListNode prev = null;

    while(n !=null){
        if(table.containsKey(new Integer(n.data))){
            prev.next = n.next;     //skip the previously stored references next node
        }else{
            table.put(new Integer(n.data) , true);
            prev = n;       //stores a reference to n
        }

        n = n.next;
    }
}

public void deleteDupsNoStorage(LinkedListNode n){
    LinkedListNode current = n;

    while(current!=null){
        LinkedListNode runner = current;
        while(runner.next!=null){
            if(runner.next.data == current.data){
                runner.next = runner.next.next;
            }else{
                runner = runner.next;
            }
        }
        current = current.next;
    }

}

public void addNode(int d){
    LinkedListNode n = new LinkedListNode(d);
    if(this.head==null){
        this.head = n;
    }else{
        n.next = head;
        head = n;
    }
}

private class LinkedListNode{
    LinkedListNode next;
    int data;

    public LinkedListNode(int d){
        this.data = d;
    }
}
}

- Peter

Answer 4

您可以使用以下Java方法来去重： 1) 时间复杂度为O(n^2)。

public void removeDuplicate(Node head) {
    Node temp = head;
    Node duplicate = null;                //will point to duplicate node
    Node prev = null;                     //prev node to duplicate node
    while (temp != null) {                //iterate through all nodes       
        Node curr = temp;
        while (curr != null) {                     //compare each one by one
            /*in case of duplicate skip the node by using prev node*/
            if (curr.getData() == temp.getData() && temp != curr) {        
                duplicate = curr;
                prev.setNext(duplicate.getNext());
            }
            prev = curr;
            curr = curr.getNext();
        }
        temp = temp.getNext();
    }
}

输入:1=>2=>3=>5=>5=>1=>3=>

输出:1=>2=>3=>5=>

2)使用哈希表，时间O(n)复杂度。

public void removeDuplicateUsingMap(Node head) {
    Node temp = head;
    Map<Integer, Boolean> hash_map = new HashMap<Integer, Boolean>(); //create a hash map
    while (temp != null) {  
        if (hash_map.get(temp.getData()) == null) {  //if key is not set then set is false
            hash_map.put(temp.getData(), false);
        } else {                                   //if key is already there,then delete the node
            deleteNode(temp,head);
        }
        temp = temp.getNext();
    }

}

public void deleteNode(Node n, Node start) {
        Node temp = start;
        if (n == start) {
            start = null;
        } else {
            while (temp.getNext() != n) {
                temp = temp.getNext();
            }

            temp.setNext(n.getNext());

        }
    }

Input:1=>2=>3=>5=>5=>1=>3=>

Output:1=>2=>3=>5=>

- Prateek Joshi

Answer 5

这是一个非常简单的版本。

LinkedList<Integer> a = new LinkedList<Integer>(){{
  add(1);
  add(1);
}}
Set<Integer> set = new HashSet<Integer>(a);
a = new LinkedList<Integer>(set);

非常简洁。不是吗？

- Alex

Answer 6

答案在C语言中。首先使用nlog时间对链表进行排序sort()，然后删除重复项del_dip()。

node * partition(node *start)
{
    node *l1=start;
    node *temp1=NULL;
    node *temp2=NULL;
    if(start->next==NULL)
        return start;

    node * l2=f_b_split(start);
      if(l1->next!=NULL)
        temp1=partition(l1);
      if(l2->next!=NULL)
            temp2=partition(l2);

if(temp1==NULL || temp2==NULL)
    {
        if(temp1==NULL && temp2==NULL)
        temp1=s_m(l1,l2);

        else if(temp1==NULL)
        temp1=s_m(l1,temp2);

        else if(temp2==NULL)
        temp1=s_m(temp1,l2);
}
    else
            temp1=s_m(temp1,temp2);

    return temp1;
}

node * sort(node * start)
{
    node * temp=partition(start);
        return temp;
}

void del_dup(node * start)
{
  node * temp;
    start=sort(start);
    while(start!=NULL)
        {
        if(start->next!=NULL && start->data==start->next->data  )
            {
                temp=start->next;
                start->next=start->next->next;
                free(temp);
            continue;
            }
        start=start->next;
        }
}

void main()
 {
    del_dup(list1);
    print(list1);
} 

- Aditya_G

Answer 7

尝试这个方法，它可以有效删除你的链表中重复的元素。

package com.loknath.lab;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class Task {
    public static void main(String[] args) {

        LinkedList<Integer> list = new LinkedList<Integer>();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(3);
        list.addLast(3);
        list.addLast(4);
        list.addLast(4);
        deleteDups(list);
        System.out.println(list);
    }

    public static void deleteDups(LinkedList<Integer> list) {
        Set s = new HashSet<Integer>();
        s.addAll(list);
        list.clear();
        list.addAll(s);

    }
}

- loknath

---

我认为这里的用户希望编写自己的链表实现，然后去除重复项，而不仅仅是使用JAVA API中的LinkedList类来去除重复项。 - user641887

除了使用JAVA API之外，将列表添加到集合中会对元素进行排序。这与处理未排序列表的问题陈述相矛盾。 - Monil Panchal

Answer 8

I think you can just use one iterator current to finish this problem 

public void compress(){
    ListNode current = front;
    HashSet<Integer> set = new HashSet<Integer>();
    set.add(current.data);
    while(current.next != null){
       if(set.contains(current.next.data)){
          current.next = current.next.next;         }
         else{
            set.add(current.next.data);
            current = current.next;
         }
      }

}

- Big_t boy

Answer 9

/**
*
* Remove duplicates from an unsorted linked list.
*/
public class RemoveDuplicates {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<String>();
        list.add("Apple");
        list.add("Grape");
        list.add("Apple");
        HashSet<String> set = removeDuplicatesFromList(list);
        System.out.println("Removed duplicates" + set);
    }
    public static HashSet<String> removeDuplicatesFromList(LinkedList<String> list){
        HashSet<String> set = new LinkedHashSet<String>();
        set.addAll(list);
        return set;
    }
}

- Gaya3

Answer 10

以上提供的所有解决方案看起来都很优化，但大多数都将自定义节点作为解决方案的一部分进行定义。这里提供了一个简单实用的解决方案，使用Java的LinkedList和HashSet，不限制使用预先存在的库和方法。

时间复杂度：O(n)

空间复杂度：O(n)

@SuppressWarnings({ "unchecked", "rawtypes" })
private static LinkedList<?> removeDupsUsingHashSet(LinkedList<?> list) {

    HashSet set = new HashSet<>();
    for (int i = 0; i < list.size();) {
        if (set.contains(list.get(i))) {
            list.remove(i);
            continue;
        } else {
            set.add(list.get(i));
            i++;
        }
    }
    return list;
}

这也保留了列表顺序。

- Monil Panchal