Java分裂整數鏈接列表

Question

我需要編寫一個方法，開始於一個單一的整數鏈表和一個稱爲分裂值的特殊值。列表中的元素沒有特定的順序。該方法將節點分爲兩個鏈接列表：一個包含所有包含小於拆分值的元素的節點和一個包含所有其他節點的節點。如果原始鏈表具有任何重複的整數（即，任何兩個或多個節點中具有相同的元素），則具有此元素的新鏈接列表應具有相同數量的重複該元素的節點。該方法返回兩個頭引用 - 一個用於每個創建的鏈接列表。

我已經花了無數小時試圖得到這個權利，並認爲這是最接近的，但編譯時我有一個錯誤，我的copyTail * IntNodes可能無法初始化。我也可能是完全錯誤的我的代碼.... 任何幫助指向我在正確的方向？

public static IntNode[ ] listSplitLessGreater(IntNode source, int splitter) 
{ 
    IntNode copyHeadLess; 
    IntNode copyTailLess; 
    IntNode copyHeadGreater; 
    IntNode copyTailGreater; 
    IntNode[ ] answer = new IntNode[2]; 
    boolean less = true; 
    boolean greater = true; 

    // Handle the special case of the empty list. 
    if (source == null) 
    return answer; // The answer has two null references . 

    //Split list into two lists less and greater/equal than splitter.  
    while (source.link != null) 
    { 
    if (splitter < source.data) 
     { 
      if (less) 
      { 
      copyHeadLess = new IntNode(source.data, null); 
      copyTailLess = copyHeadLess; 
      less=false; 
      } 
      else 
      { 
      source = source.link; 
      copyTailLess.addNodeAfter(source.data); 
      copyTailLess = copyTailLess.link; 

      } 
     } 
     else 
     { 
      if (greater) 
      { 
      copyHeadGreater = new IntNode(source.data, null); 
      copyTailGreater = copyHeadGreater; 
      greater=false; 
      } 
      else 
      { 
      source = source.link; 
      copyTailGreater.addNodeAfter(source.data); 
      copyTailGreater = copyTailGreater.link; 

      } 
     } 

    }  

    //Return Head References 
    answer[0] = copyHeadLess; 
    answer[1] = copyHeadGreater; 

    return answer; 

}

Answer 1

我認爲你正在做的複雜得多，它需要的，通過模擬一個列表只是一個單獨的類（IntNode）。如果您將它建模爲「列表」和「列表中的一個節點」，那麼很容易得到一個空的列表。你也不需要跟蹤頭部和尾部 - 列表可以做到這一點。在這一點上，這是非常簡單的：

• 創建兩個空列表，一個「低級」和一個「不低」
• 遍歷原來的列表：
  • 制定出哪個列表添加該元素
  • 添加元素
• 返回兩個列表（例如使用爲你做了一個數組）

請注意，即使沒有這些，只需使用null來表示「我還沒有這個列表」即可。目前您的代碼無法編譯，因爲copyHeadLess等不是，當它們被使用時，它們明確指定爲。 你知道你不會嘗試使用它們，直到它們被分配，但編譯器不會。儘管如此，我仍然推薦重構方法:)

Answer 2

如果source不爲null，但source.link爲null（list僅由一個元素組成），那麼您絕對不會指定給您的copyHeadLess等變量。嘗試將它們初始化爲空或默認值爲：

IntNode copyHeadLess = null; 
    IntNode copyTailLess = null; 
    IntNode copyHeadGreater = null; 
    IntNode copyTailGreater = null; 
    IntNode[ ] answer = new IntNode[2]; 
    boolean less = true; 
    boolean greater = true; 

    // Handle the special case of the empty list.  
    if (source == null) 
    return answer; // The answer has two null references . 

    //Split list into two lists less and greater/equal than splitter.  
    while (source.link != null) 
    { 
    // what about case where source isn't null but source.link is null? 
    }  

    //Return Head References 
    answer[0] = copyHeadLess; // this may have never been assigned in your original code 
    answer[1] = copyHeadGreater; // this may have never been assigned in your original code 

    return answer; 

}