Find the number of duplicates in a LinkedList - an edge case test failing

user_19413610 0
Viewed 63

I was asked to code for the following problem:

Problem Description:

Given a linked list, find the number of duplicate elements in the list.

Input Format:

First line contains an integer N - The number of nodes.

Second line contains N integers - Node values.

Output Format:

Print the total number of duplicates.

Constraints:

N <= 10^5

Value of node <= 10^6

Sample Input:

9

1 2 3 4 4 5 6 6 6

Sample Output:

3

Explanation:

In the given test case we have 3 duplicates i.e. one 4 and two 6.

My code:

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

I want to understand why my code is failing the edge case.

singly-linked-list linked-list algorithm java
1 Answers

When the head-node is null your code will produce a NullPointerException when it enters the outer while-loop (while evaluating the condition head.next != null, which will fail if head is null).

Also, your solution is inefficient. You're checking every value against all others values in the list and takes a quadratic time O(n^2) to run.

This problem can be solved in a liner time O(n), in a single pass through the list and fewer code.

For that, you can utilize a HashSet which will store every previously encountered value. If an offered value rejected by the set, i.e. seen.add() returns false, that means this value is a duplicate.

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: it's not considered to be a good practice to modify objects received as method parameters.

user_179499450
Related