Let m be a postive integer and L a sorted single linked list of integers. for each integer k, if k appears more than m times in L, remove all node from L containing k.

as per my understanding if the input is

L = 1 --> 2 -->2-->2 -->2 --> 3--> Null
K =2

so any number should not be more than 2 times. here 2 is repeating 3 times, hence it should remove all 2. so output should be like

output : 1-->3--> NULL

when i refer this solution in internet someone posted answer saying output should be like

1-->2-->3--> NULL.

could you please post understanding about this problem ?

i know this is very silly question. please try if you have time. if you know solution also good.

where i can find EPI problem variant solution

CodePudding user response：

Mainly, need to check occurrences and create a new list based on. Now if need only non-repetitive or just distinct need to clear yourself.

    List<Integer> l = new LinkedList<>();
    List<Integer> result = new LinkedList<>();
    List<Integer> result2 = new LinkedList<>();

    Collections.addAll(l, 1,2,2,3);
    
    //non-repetitive
    for(Integer i : l.stream().distinct().collect(Collectors.toList()))
    {
        if(Collections.frequency(l, i)==1)
        {
            result.add(i);
        }
    }
    result.forEach(System.out::println);
    
    //distinct (or non-repetitive)
    //just to have an alternative approach for counting
    Map<Integer, Long> counts =l.stream().
                       collect(Collectors.groupingBy(e -> e, Collectors.counting()));
    for(Integer i: counts.keySet())
    {
        //non-repetitive
        //if(counts.get(i)==1) result2.add(i);
        result2.add(i);
    }
    result2.forEach(System.out::println);

Result:

non-repetitive: 1,3
distinct: 1,2,3

Note: This is a working solution, not necessary the optimal one. Also didn't follow description to work just on initial list. Since didn't provide any code should adapt yourself.

Another approach can be to iterate over initial-list keeping track of previous element and proceed based on and the current. (keep or delete nodes)

CodePudding user response：

i implemented this solution. please check

public Node remove(Node head, int k) {
        Node iter = head;
        Node prev = null;
        while (iter != null) {
            int i = 1;
            Node distrinct = iter.next;
            while (distrinct != null && distrinct.data == iter.data) {
                i  ;
                distrinct = distrinct.next;
            }
            /*there is no element within given range */
            if (prev == null && distrinct == null)
                return null;

            if (i >= k) {
                if (prev == null) {
                    head = distrinct;
                } else {
                    prev.next = distrinct;
                }
            } else {
                prev = iter;
            }
            iter = distrinct;
        }
        return head;
    }