java - 如何找到两个单链表的交集

Question

我正在编写一个程序，其中我必须设置数据结构字典(单链表)，其中单词按字母顺序排列(出现在带有文档 ID 的文本文档的句子中的单词)。并找出哪些单词出现在多个文档中，以便教授希望我们进行交集。我真的很困惑如何做交叉点。我还有其他一切(我相信这是正确的)。这是我的代码(我添加了相交算法，但它显然不起作用，我遵循了教授的算法[她从未向我们展示过示例]):

public class dictionary 
{
  //variables
  dNode head;
  int size;

  //constructor
  public dictionary() 
  {
    head = null;
    size = 0;
  }

  //addFirst method
  public void addFirst(dNode s) 
  {
    s.setNext(head);
    head = s;
    size++;
  }

  public void addLast(dNode s)
  {
    if ( head == null )
    {
      head = s;
    }
    else
    {
      s.setNext(null);
      dNode w = head;
      while ( w.getNext() != null ) 
      { 
        w = w.getNext();
      }
      w.setNext(s);
    }
      size++;
  }

  //toString Method
  public String toString() 
  {
    String w = "";
    dNode s = head;
    while ( s != null ) 
    {
      w += s + "\n";
      s = s.getNext();
    }
    return w;
  }

  //intersection method
public String intersection(pNode head, dNode head) {
int left = posting.head;
int right = dictionary.head;
int result = new dictionary();

while (left != null && right != null) {
     if (dID.left < dID.right) {
     left = left.next;
else if (dID.left > dID.right)
     right = right.next;
else 
     left = left.next;
     right = right.next;
     result.push(left.data() );
     }
}
return result;
}  
}


public class dNode 
{
  //variables
  String sent;
  posting post;
  dNode nextNode;

  //constructor
  public dNode(String sent, posting post, dNode nextNode)
  {
    this.sent = sent;
    this.post = post;
    this.nextNode = nextNode;
  }

  //returns element of this node
  public String getSent() {
    return sent;
  }

  //retunrs the next node of this node
  public dNode getNext() {
    return nextNode;
  }

  //modifier methods
  //sets elements of this node.
  public void setSent(String newSent) {
    sent = newSent;
  }

  //sets the next node of this node
  public void setNext( dNode newNext) {
    nextNode = newNext;
  }
  //toString method
  public String toString() 
  {
    return "Sentence and Posting: \n" + sent + "\n" + post;
  }
}


public class pNode {
  //variables
  int dID;
  String word;
  int occurence;
  pNode next;

  //constructor
  public pNode(int dID, String word, int occurence, pNode next)
  {
    this.dID = dID;
    this.word = word;
    this.occurence = occurence;
    this.next = next;
  }
  //return element of this node
  public String getWord() {
    return word;
  }

  //Returns the next node of this node
  public pNode getNext() {
    return next;
  }

  //Modifier methods
  //set the words of this node
  public void setWord(String newWord) {
    word = newWord;
  }

  //sets the next node of this node
  public void setNext(pNode newNext){
    next = newNext;
  }

  //toString method
  public String toString() {
    return "Document ID, Word, Occurence: \n " + dID + ", " 
      + word + ", " + occurence;
  }

}


public class posting 
{
  //variables
  pNode head;
  int size;

  //constructor
  public posting() 
  {
    head = null;
    size = 0;
  }

  //addFirst method 
  public void addFirst(pNode s) 
  {
    s.setNext(head);
    head = s;
    size++;
  }

  //addLast method
  public void addLast(pNode s)
  {
    if ( head == null )
    {
      head = s;
    }
    else
    {
      s.setNext(null);
      pNode w = head;
      while ( w.getNext() != null ) 
      {
        w = w.getNext();
      }
      w.setNext(s);
    }
    size++;
  }

  //toString method
  public String toString()
  {
    String w = "";
    pNode s = head;
    while ( s != null) 
    {
      w += s + "\n";
      s = s.getNext();
    }
    return w;
  }
}

import java.io.*;
import java.util.*;

  public class testFile
  {

  public static void main (String[] args) throws FileNotFoundException 
  {
    File filename = new File("/export/home/hawkdom2/s0878044/CS503/assignment2/sentences.txt");
    Scanner scan = new Scanner(filename);
    dictionary Dictionary = new dictionary();

   while ( scan.hasNextLine() )
   {
     String sentence = scan.nextLine();
     String[] word = sentence.split(" ");

     //first element is document id
     int dID = Integer.parseInt( word[0] );

     //insertion sort
     for ( int i = 2; i < word.length; i++ )
     {
       for ( int j = i; j > 1; j-- )
       {
        if ( word[j].compareTo( word[j-1] ) > 0 )
        {
          String switchs = word[j];
          word[j] = word[j-1];
          word[j-1] = switchs;
        }
       }
     }

     //integer array count
     int[] count = new int[word.length];
     for ( int i = 1; i < word.length; i++)
     {
       for ( int j = 1; j < word.length; j++)
       {
         if (word[i].equalsIgnoreCase( word[j] ) )
         {
           count[i]++;
         }
       }
     }

     posting posts = new posting();

     for ( int i = 1; i < word.length; i++ )
     {
       if ( (i > 1 ) && (word[i].equalsIgnoreCase( word[i-1] ) ) )
         continue;
       else
       {
         posts.addFirst(new pNode(dID, word[i], count[i], null) );
       }
     }

     Dictionary.addLast(new dNode(sentence, posts, null) );
   }





   //print out output
   System.out.println(Dictionary);
  }
  }

这是句子文件:

1 a rose is a rose 
2 John chased a cat and the cat chased John
3 cats are mammals but mammals are not cats
4 beavers build dams but i know a beaver that does not
5 my dog chased a cat and the cat attacked my dog
6 my dog likes cats but my cat dislikes dogs
7 my dog likes roses but roses dislike my dog
8 my cat dislikes roses but roses like my cat
9 red roses are not my favorite roses
10 my favorite roses are pink roses

如果我能深入了解如何使两个链接列表相交(或者我的程序是否有其他问题)，我将非常感激。我上周生病了，我的教授拒绝帮助我解决我错过的事情(如果我生病时不来上课，显然我不是一个认真的程序员)。我真的无法忍受这位教授教授这门课的方式，因为她没有给我们任何程序示例(而且她给我们的极少数程序总是有错误)。她还只是给了我们算法，她已经说过，它们并不总是正确的。我曾经喜欢编程，但她真的让我对它失去了兴趣，我现在想做的就是至少获得一个 C，这样我就可以转向 IT。如果有人可以帮助我，我将非常感激，我非常想完成这门课，而不必再接受这位教授的指导。

我添加了一个相交方法，但仍然收到所有这些错误:发现7个错误:文件:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [行:86]错误:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86:表达式的非法开始文件:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [行:86]错误:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86:“；”预期的文件:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [行:86]错误:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86:不是语句文件:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [行:86]错误:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86:“；”预期的文件:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [行:86]错误:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86:不是语句文件:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [行:86]错误:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86:“；”预期的文件:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [行:96]错误:/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:96:“else”没有“if”

Answer 1

public static void findIntersection(LLNode head1, LLnode head2)
    {
        HashSet<LLNode> hs= new HashSet<>();
        HashSet<LLNode> hs2 = new HashSet<>();
        LLNode currentNode1 = head1; 

        while(currentNode.getNext()!=null)
        {
            hs.add(currentNode);
            currentNode1 = currentNode1.getNext();
        }

        LLNode currentNode2 = head2;
        while(currentNode2.getNext()!=null)
        {  
        if(hs1.contains(currentNode2)){
             hs2.add(currentNode2);
         }
        }