Java -计算链表中的出现次数

Question

作为赋值的一部分，我必须编写一个方法来打印链表中的重复值，以及它们出现的次数。下面是使用辅助方法countRepeats(ListNode node)的方法printRepeats()。

问题是我的方法的输出一遍又一遍地打印重复的值。例如"1 1 1 2 3 4 5 6 7 6"列表，输出结果为"1 (Occurences = 3) 1 (Occurences = 3) 1 (Occurences = 3) 6 (Occurences = 2) 6 (Occurences = 2)"。任何重复的值应该只打印一次。有什么建议吗?提前感谢!

public class LinkedList
{
    private ListNode first;
    public void printRepeats()
    {
        String ans = "";
        ListNode temp = first;
        while(temp != null)
        {
            if(countRepeats(temp) > 1 && ans.indexOf((int)temp.getValue()) == -1)
            {
                ans += temp.getValue();
                System.out.print(temp.getValue() + " (Occurences = " + countRepeats(temp) + ") ");
            }
            temp = temp.getNext();
        }
        if(ans.length() == 0)
            System.out.print("None of the elements repeat.");
    }
    private int countRepeats(ListNode node)
    {
        ListNode temp = first;
        int count = 0;
        while(temp != null)
        {
            if((int)temp.getValue() == (int)node.getValue())
                count++;
            temp = temp.getNext();
        }
        return count;
    }
}   

Answer 1

考虑到除了LinkedList不能使用任何其他数据结构，您可以:

• 创建另一个ListNode元素作为一个名为"repeatedElements"的列表的第一个元素，该元素必须包含该元素的成对元素/重复元素。
• 当计算单个元素的重复次数时，将该元素及其重复次数插入到"repeatedElements"列表中。
• 在计算一个元素的重复次数之前，先在repeatedElements列表中查找该元素。如果元素存在，则不打印输出。如果不是，像往常一样重复代码。

我所描述的系统将包含比具体需要的更多的信息(存储每个元素的重复次数)，但是很可能再次需要它。

Answer 2

对于计数出现，您需要维护访问节点的跟踪记录，也像如果您已经计数任何节点，那么不需要再次选择那些出现在链接列表中。下面的程序清楚地解释了这一点-

import java.util.ArrayList;
public class CustomLinkList {
    public static void main(String[] args) {
        ListNode linkedList = new ListNode(15);
        linkedList.next =new ListNode(67);
        linkedList.next.next =new ListNode(15);
        linkedList.next.next.next =new ListNode(65);
        linkedList.next.next.next.next =new ListNode(13);
        linkedList.next.next.next.next.next =new ListNode(98);
        linkedList.next.next.next.next.next.next =new ListNode(33);
        linkedList.next.next.next.next.next.next.next =new ListNode(29);
        linkedList.next.next.next.next.next.next.next.next =new ListNode(15);
        ListNode printList = linkedList;
        System.out.println("Custom Link List is ::: ");
        while (printList.next != null){
            System.out.printf("%d ",printList.info);
            printList = printList.next;
        }
        System.out.println();
         CustomLinkList.occurancesOfElement(linkedList);
    }
    public static void occurancesOfElement(ListNode listNode){
        ArrayList<Integer> visitedNode = new ArrayList();
        while(listNode !=null){
            ListNode node = listNode;
            int count = 0;
            while (node !=null)
            {
                if(listNode.info == node.info && !visitedNode.contains(node.info)) {
                    count++;
                }
                node = node.next;
            }
            if(!visitedNode.contains(listNode.info))
            System.out.println("Occurences of : "+listNode.info+" is "+ count);
            
            visitedNode.add(listNode.info);
            listNode = listNode.next;
        }
    }
}
class ListNode {
    int info;
    ListNode next;
    ListNode(int info){
        this.info = info;
        next = null;
    }
}
class DoublyListNode {
    int info;
    DoublyListNode previous;
    DoublyListNode next;
}
}