Java 拆分整数链表

Question

我需要编写一个以单个整数链表和称为拆分值的特殊值开头的方法。列表的元素没有特定的顺序。该方法将节点划分为两个链表：一个包含包含小于拆分值的元素的所有节点，另一个包含所有其他节点。如果原始链表有任何重复的整数(即，任何两个或多个节点中具有相同的元素(，那么具有此元素的新链表应具有相同数量的重复此元素的节点。该方法返回两个 head 引用 - 每个创建的链接列表一个。

我花了无数个小时试图做到这一点，并认为这是最接近的，但我在编译时遇到错误，我的 copyTail* IntNode 可能无法初始化。我的代码也可能完全错误....有什么帮助指向我正确的方向吗？？

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 不是空的，但 source.link 是空的(list 只由一个元素组成(，那么你永远不会给 copyHeadLess 等变量赋值。尝试将它们初始化为 null 或任何默认值：

  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; 
 }