在linkedlist中找到重复的数量 - 边缘案例测试失败

Question

我被要求编码以下问题：

问题描述：

给定链接列表，在中找到重复元素的数量 列表。

输入格式：

第一行包含一个整数n - 节点的数量。

第二行包含n整数-Node values 。

输出格式：

打印重复的总数。

约束：

n＆lt; = 10^5

node＆lt; = 10^6

的值

示例输入：

9

1 2 3 4 4 5 6 6 6

< < em>示例输出：

3

说明：

在给定的测试用例中，我们有3重复项，即一个4和两个6。

我的代码：

import crio.ds.List.*;
    
    /*public class ListNode {
       public int val;
       public ListNode next;
       public ListNode(int x) { val = x; next = null; }
    }*/
    
    
    public class Solution {
        public int countDuplicatesInALinkedList(ListNode head){
    
            int counter = 0;
            
            while(head.next != null){
    
                ListNode ptr = head.next;
                while(ptr != null){
                    if(head.val == ptr.val){
                        counter++;
                        break;
                    }
                    ptr = ptr.next;
                }
                head = head.next;
            }
            
            return counter;
        }
    }

我想了解为什么我的代码失败了边缘情况。

Answer 1

当 head-node 是null您的代码将产生nullpoInterException当它输入ofter 时， -loop（ 在评估条件head.next！= null时，如果头为null ）。

另外，您的解决方案效率低下。您正在检查列表中所有其他值的每个值，并需要一个二次时间 o（n^2）运行。

可以在列表中的单个通过和更少的代码中，可以在衬里时间 o（n）中解决此问题。

为此，您可以使用Hashset，该将存储每个先前遇到的值。如果 set 拒绝的提供的值，即see.add（）返回false，则意味着此值是重复的。

public int countDuplicatesInALinkedList(ListNode head) {
    
    Set<Integer> seen = new HashSet<>();
    int counter = 0;
    
    ListNode current = head;
    
    while (current != null) {
        if (!seen.add(current.val)) { // value has been rejected - i.e. it's a duplicate
            counter++;
        }
        current = current.next;
    }
    return counter;
}

sideNote：，不认为将接收到方法参数的对象修改为一个好习惯。