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

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 table=new Hashtable(); 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 list=new LinkedList(); 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]

它不会消除重复。

为什么方法不起作用？

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

Answer 2

1. 您提供的解决方案不会修改原始列表。
2. 要修改原始列表并删除重复项，我们可以使用两个指针进行迭代。 Current：迭代LinkedList，以及用于检查所有后续节点是否重复的运行器。

3. 下面的代码在O（1）空间中运行，但是在O（N平方）时间内运行。

   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

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 table = new Hashtable(); 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; } } } 

Answer 4

Ans在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); } 

Answer 5

试试这个它正在用于删除linkedList中的重复元素

 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 list = new LinkedList(); 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 list) { Set s = new HashSet(); s.addAll(list); list.clear(); list.addAll(s); } } 

Answer 6

 I think you can just use one iterator current to finish this problem public void compress(){ ListNode current = front; HashSet set = new HashSet(); 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; } } 

}

Answer 7

您可以使用以下java方法删除重复项：

1） complexity为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）的 complexity 。

 public void removeDuplicateUsingMap(Node head) { Node temp = head; Map hash_map = new HashMap(); //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()); } } 

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

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

Answer 8

第一个问题是

 LinkedListNode head=new LinkedListNode(list.getFirst()); 

实际上并没有用list的内容初始化head 。 list.getFirst()只返回Integer 1 ， head包含1作为唯一元素。 您必须通过循环遍历list来初始化head以获取所有元素。

另外，虽然

 Task.deleteDups(head) 

修改head ，这使得list完全不变 – 没有理由为什么head的更改应该传播到list 。 因此，要检查您的方法，您必须循环向下并打印出每个元素，而不是再次打印出list 。

Answer 9

试试吧。它正在运作。 //删除链接列表中的重复项

 import java.io.*; import java.util.*; import java.text.*; class LinkedListNode{ int data; LinkedListNode next=null; public LinkedListNode(int d){ data=d; } void appendToTail(int d){ LinkedListNode newnode = new LinkedListNode(d); LinkedListNode n=this; while(n.next!=null){ n=n.next; } n.next=newnode; } void print(){ LinkedListNode n=this; System.out.print("Linked List: "); while(n.next!=null){ System.out.print(n.data+" -> "); n=n.next; } System.out.println(n.data); } } class LinkedList2_0 { public static void deletenode2(LinkedListNode head,int d){ LinkedListNode n=head; // If It's head node if(n.data==d){ head=n.next; } //If its other while(n.next!=null){ if(n.next.data==d){ n.next=n.next.next; } n=n.next; } } public static void removeDuplicateWithBuffer(LinkedListNode head){ LinkedListNode n=head; LinkedListNode prev=null; Hashtable table = new Hashtable(); while(n!=null){ if(table.containsKey(n.data)){ prev.next=n.next; } else{ table.put(n.data,true); prev=n; } n=n.next; } } public static void removeDuplicateWithoutBuffer(LinkedListNode head){ 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; } } public static void main(String[] args) throws java.lang.Exception { LinkedListNode head=new LinkedListNode(1); head.appendToTail(1); head.appendToTail(3); head.appendToTail(2); head.appendToTail(3); head.appendToTail(4); head.appendToTail(5); head.print(); System.out.print("After Delete: "); deletenode2(head,4); head.print(); //System.out.print("After Removing Duplicates(with buffer): "); //removeDuplicateWithBuffer(head); //head.print(); System.out.print("After Removing Duplicates(Without buffer): "); removeDuplicateWithoutBuffer(head); head.print(); } } 

Answer 10

这里有几个其他解决方案（与Cracking coding inerview略有不同，更容易阅读IMO）。

 public void deleteDupes(Node head) { Node current = head; while (current != null) { Node next = current.next; while (next != null) { if (current.data == next.data) { current.next = next.next; break; } next = next.next; } current = current.next; } 

}

 public void deleteDupes(Node head) { Node current = head; while (current != null) { Node next = current.next; while (next != null) { if (current.data == next.data) { current.next = next.next; current = current.next; next = current.next; } else { next = next.next; } } current = current.next; } 

}

Answer 11

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

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

非常简洁。 不是吗？

Answer 12

没有HashSet或创建Node的方法很简单。

 public String removeDuplicates(String str) { LinkedList chars = new LinkedList(); for(Character c: str.toCharArray()){ chars.add(c); } for (int i = 0; i < chars.size(); i++){ for (int j = i+1; j < chars.size(); j++){ if(chars.get(j) == chars.get(i)){ chars.remove(j); j--; } } } return new String(chars.toString()); } 

并validation它：

 @Test public void verifyThatNoDuplicatesInLinkedList(){ CodeDataStructures dataStructures = new CodeDataStructures(); assertEquals("abcdefghjk", dataStructures.removeDuplicates("abcdefgabcdeaaaaaaaaafabcdeabcdefgabcdbbbbbbefabcdefghjkabcdefghjkghjkhjkabcdefghabcdefghjkjfghjkabcdefghjkghjkhjkabcdefghabcdefghjkj") .replace(",", "") .replace("]", "") .replace("[", "") .replace(" ", "")); } 

Answer 13

 LinkedList list = new LinkedList(); for(int i=0; ij){ list.remove(i); if(list.get(i) != null){ list.get(j).next = list.get(i); }else{ list.get(j).next = null; } } } } } } 

Answer 14

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

Answer 15

下面的代码实现了这个，不需要任何临时缓冲 它首先比较第一个和第二个节点，如果不是匹配，它将第一个节点的char添加到第二个节点，然后将第二个节点中的所有字符比较到第三个节点的char，依此类推。 comperison完成后， 在离开节点之前，它会清除添加的所有内容并恢复其驻留在node.val.char（0）的旧值

F> FO> FOL>（匹配找到，node.next = node.next.next）>（再次匹配，丢弃它）> FOLW> ….

 public void onlyUnique(){ Node node = first; while(node.next != null){ for(int i = 0 ; i < node.val.length(); i++){ if(node.val.charAt(i) == node.next.val.charAt(0)){ node.next = node.next.next; }else{ if(node.next.next != null){ //no need to copy everything to the last element node.next.val = node.next.val + node.val; } node.val = node.val.charAt(0)+ ""; } } node = node.next; } } 

Answer 16

上面给出的所有解决方案看起来都是优化的，但大多数解决方案将自定义节点定义为解决方 这是一个使用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; } 

这也保留了列表顺序。

Answer 17

1. 完全动态方法 2. 从LinkedList删除重复项 3. LinkedList基于动态对象的创建 谢谢

 import java.util.Scanner; class Node{ int data; Node next; public Node(int data) { this.data=data; this.next=null; } } class Solution { public static Node insert(Node head,int data) { Node p=new Node(data); if(head==null) { head=p; } else if(head.next==null) { head.next=p; } else { Node start=head; while(start.next!=null) { start=start.next; } start.next=p; return head; //System.out.println(); } return head; } public static void display(Node head) { Node start=head; while(start!=null) { System.out.print(start.data+" "); start=start.next; } } public static Node remove_duplicates(Node head) { if(head==null||head.next==null) { return head; } Node prev=head; Node p=head.next; while(p!=null) { if(p.data==prev.data) { prev.next=p.next; p=p.next; } else{ prev=p; p=p.next; } } return head; } public static void main(String args[]) { Scanner sc=new Scanner(System.in); Node head=null; int T=sc.nextInt(); while(T-->0) { int ele=sc.nextInt(); head=insert(head,ele); } head=remove_duplicates(head); display(head); } } 

输入：5 1 1 2 3 3输出：1 2 3