时间戳

首页 > 解决方案 > 删除链表中的重复项

java - 删除链表中的重复项

问题描述

我在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

它没有按预期删除重复项

ptr1.data == ptr2.data我尝试在 vscode 中对其进行调试，并惊讶地发现false当 ptr1 为 386 而 ptr2 在输入的第一个 386 之后为 386 时，我也尝试了 LinkedListNode 的 getter ptr1.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;   
}

input:281 386 386 957 1022 1216 1232 1364 1428 1428 1428 1428 1501 1953 -1 输入-1后停止接受输入并返回生成链表的头部

标签： javalinked-list

解决方案

应该有循环2 While来选择一个元素并检查. 以下代码可以帮助您更好地理解。elementLinked List

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;

推荐阅读