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]
它不会消除重复。
为什么这个方法不起作用？
迭代链表，将每个元素添加到哈希表中。当我们发现重复元素时，我们删除元素并继续迭代。我们可以在一次通过中完成所有操作，因为我们使用链表。
以下解决方案需要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;
}
}
这里有几个其他解决方案（与Cracking编码采访略有不同，更容易阅读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;
}
}
这是一个非常简单的版本。
LinkedList<Integer> a = new LinkedList<Integer>(){{
add(1);
add(1);
}}
Set<Integer> set = new HashSet<Integer>(a);
a = new LinkedList<Integer>(set);
LinkedList<Integer> a = new LinkedList<Integer>(){{
add(1);
add(1);
}}
Set<Integer> set = new HashSet<Integer>(a);
a = new LinkedList<Integer>(set);
非常简洁。不是吗？
这是没有HashSet或创建Node的简单方法。
public String removeDuplicates(String str) {
LinkedList<Character> chars = new LinkedList<Character>();
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());
}
并验证它：
@Test
public void verifyThatNoDuplicatesInLinkedList(){
CodeDataStructures dataStructures = new CodeDataStructures();
assertEquals("abcdefghjk", dataStructures.removeDuplicates("abcdefgabcdeaaaaaaaaafabcdeabcdefgabcdbbbbbbefabcdefghjkabcdefghjkghjkhjkabcdefghabcdefghjkjfghjkabcdefghjkghjkhjkabcdefghabcdefghjkj")
.replace(",", "")
.replace("]", "")
.replace("[", "")
.replace(" ", ""));
}
LinkedList<Node> list = new LinkedList<Node>();
for(int i=0; i<list.size(); i++){
for(int j=0; j<list.size(); j++){
if(list.get(i).data == list.get(j).data && i!=j){
if(i<j){
list.remove(j);
if(list.get(j)!= null){
list.get(j-1).next = list.get(j);
}else{
list.get(j-1).next = null;
}
}
else{
if(i>j){
list.remove(i);
if(list.get(i) != null){
list.get(j).next = list.get(i);
}else{
list.get(j).next = null;
}
}
}
}
}
}
/**
*
* 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;
}
}
下面的代码实现了这个，不需要任何临时缓冲它首先比较第一个和第二个节点，如果不匹配，它会将第一个节点的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;
}
}
上面给出的所有解决方案都看似优化，但大多数解决方案将自定义Node定义为解决方案的一部这是一个使用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;
}
这也保留了列表顺序。
1.Fully Dynamic Approach 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
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
这是在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;
}
}
}
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);
}
尝试这样做是为了删除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<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);
}
}
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;
}
}
}
您可以使用以下java方法删除重复项：
1）使用O（n ^ 2）的complexity
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<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());
}
}
输入：1 => 2 => 3 => 5 => 5 => 1 => 3 =>
输出：1 => 2 => 3 => 5 =>
第一个问题是
LinkedListNode head=new LinkedListNode(list.getFirst());
实际上并没有用head的内容初始化list。 list.getFirst()只返回整数1，head包含1作为唯一元素。你必须通过循环head初始化list以获得所有元素。
另外，虽然
Task.deleteDups(head)
修改head，这使list完全不变 - 没有理由为什么head的变化应该传播到list。因此，要检查您的方法，您必须循环head并打印出每个元素，而不是再次打印出list。
试试吧。它工作。 //删除链接列表中的重复项
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<Integer, Boolean> table = new Hashtable<Integer, Boolean>();
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();
}
}