常规链表查找重复项

Question

大家好，

我正在学习Bsc IT，但遇到了问题。在目前新冠肺炎的情况下，我们基本上只能自学，我需要有人用我的代码把我带到正确的方向(而不是给我答案(。

我必须编写一个名为appearsTwice的程序，该程序接收一个作为参数的链表，并返回另一个包含参数列表中出现两次或多次的所有项目的列表。

到目前为止我的代码(我的想法是否正确？我必须看什么？(

公共MyLinkedList出现两次(MyLinkedListparamList(

{
MyLinkedList<E> returnList = new MyLinkedList<E>(); // create an empty list

Node<E> ptrThis = this.head;//Used to traverse calling list
Node<E> ptrParam= paramList.head; //neither lists are empty
if (paramList.head == null) // parameter list is empty
return returnList;
if (ptrThis == null) //Calling list is empty
return returnList;
for (ptrThis = head; ptrThis != null; ptrThis = ptrThis.next)
{
if (ptrThis == ptrThis.element)
{
returnList.append(ptrThis.element); 
}
}    

Answer 1

一些问题：

• 您的代码从不遍历参数列表。访问的唯一节点是它的头节点。您需要对调用列表中找到的每个值的参数列表进行迭代(假设不允许使用哈希集等其他数据结构(。

• if (ptrThis == ptrThis.element)没有什么意义：它试图将节点与节点值进行比较。在实践中，这永远不会是真的，也不会有用。您希望将ptrParam.element与ptrThis.element进行比较，前提是您有一个ptrParam沿参数列表移动的迭代。

• for循环之后没有return语句。。。

• 您需要一个计数器来满足匹配必须至少发生两次的要求。

这里有一些你可以使用的代码：

class MyLinkedList {
public MyLinkedList appearsTwice(MyLinkedList paramList) {
MyLinkedList<E> returnList = new MyLinkedList<E>();

if (paramList.head == null) return returnList; // shortcut
for (Node<E> ptrParam = paramList.head; ptrParam != null; ptrParam = ptrParam.next) {
// For each node in the param list, count the number of occurrences, 
//    starting from 0 
int count = 0;
for (Node<E> ptrThis = head; ptrThis != null; ptrThis = ptrThis.next) {
// compare elements from both nodes
if (ptrThis.element == ptrParam.element) {
count++;
if (count >= 2) {
returnList.append(ptrParam.element);
// no need to look further in the calling list 
//   for this param element
break;
}
}
}
}
return returnList; // always return the return list
}
}