删除链接列表中的重复项

Question

我在java中尝试了以下代码，以从链表中删除重复项

public static LinkedListNode<Integer> removeDuplicates(LinkedListNode<Integer> head) {
LinkedListNode<Integer> ptr1=head;
LinkedListNode<Integer> ptr2=head.next;
if(head==null)
return null;
if(head.next==null)
return head;
while(ptr2!=null){
if(ptr1.data==ptr2.data){
ptr2=ptr2.next;
}else{
ptr1.next=ptr2;
ptr1=ptr2;
ptr2=ptr2.next;
}
}
ptr1.next=ptr2;
return head;
}

其将链表的头作为输入，然后在从中去除重复之后返回头。

如果我们采用以下链接列表的样本输入

281 386 386 957 1022 1216 1232 1364 1428 1428 1428 1428 1501 1953

它没有像预期的那样删除重复项

我试着在vscode中调试它，并惊讶地发现，当ptr1位于386，ptr2位于输入的第一个386之后的386时，ptr1.data == ptr2.data的求值结果为false即使在那时，我也尝试了LinkedListNode的getterptr1.getData()==ptr2.getData()出现错误

有没有一些与内存分配有关的概念，我没有涉及堆之类的？

如果你对LinkedListNode类感到好奇以及用于创建链接列表的功能，它们是：

public class LinkedListNode<T> {
T data;
LinkedListNode<T> next;
LinkedListNode (T data){
this.data=data;
}
T getData(){
return this.data;
}
}

和

static LinkedListNode<Integer> takeinput(){
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
LinkedListNode<Integer> head = new LinkedListNode<Integer>(data);
LinkedListNode<Integer> tail = head;
data=sc.nextInt();
while(data!=-1){
LinkedListNode<Integer> newNode = new LinkedListNode<Integer>(data);
if(head.next==null){
head.next=newNode;
tail=newNode;
}else{
tail.next=newNode;
tail= newNode;
}
data=sc.nextInt();
}
sc.close();
return head;   
}

输入：281 386 386 957 1022 1216 1232 1364 1428 1428 1424 1501 1953-1它在输入-1后停止接受输入，并返回生成的链表的头

Answer 1

此更新太迟，但没有NPE:

public static LinkedListNode<Integer> removeDuplicates(LinkedListNode<Integer> head) {
if (head == null || head.next == null)
return head;
LinkedListNode<Integer> ptr1 = head;
LinkedListNode<Integer> ptr2 = head.next;
while (ptr2 != null) {
while(ptr1.data.equals(ptr2.data)) {
ptr2 = ptr2.next;
ptr1.next = ptr2;
}
ptr1.next = ptr2;
ptr1 = ptr2;
ptr2 = ptr2.next;
}
ptr1.next = ptr2;
return head;
}

Answer 2

如果我刚读过你的标题，你可以通过迭代从LinkedList中删除重复项，将值存储在Set中，并通过Set检查重复项，如果包含则返回对积分器的true调用remove。

Iterator iter = list.iterator();
Set set = new HashSet();
while (iter.hasNext())
{
Object obj = iter.next();
if(set.contains(obj))){
iter.remove();
}else{
set.add(obj);
}
}

Answer 3

应该有2 While循环来选择一个元素，并检查Linked List中是否存在element。以下代码可能有助于您更好地理解。

LinkedListNode<Integer> ptr1=head;
LinkedListNode<Integer> ptr2=head.next;
if(head==null)
return null;
if(head.next==null)
return head;
while (ptr1 != NULL && ptr1.next != NULL) // pick 1 element at time
{ 
ptr2 = ptr1; 
while (ptr2.next != NULL) 
{ 
if (ptr1.data == ptr2.next.data) // check if the element exits in LinkedList or not
{ 
dup = ptr2.next; 
ptr2.next = ptr2.next.next; 
} 
else 
ptr2 = ptr2.next; 
} 
ptr1 = ptr1.next; 
} 
return head;

Answer 4

删除重复的

list.stream().distinct().peek(System.out::println).collect(Collectors.toList());

Answer 5

在不使用额外空间的情况下，只需在链接列表中每个节点迭代一次就可以为提供服务

public void removeDupsFromLinkedList(Node head)
{
LinkedListImpl linkedListImpl = new LinkedListImpl();
if(head==null)
return;
Node temp = head;
while(temp!=null)
{
Node traverseNode = temp;
while(traverseNode!=null)
{
if(traverseNode.value==temp.value && traverseNode!=temp)
linkedListImpl.deleteNode(traverseNode);
traverseNode=traverseNode.next;
}
temp = temp.next;
}
}