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 等在使用时未明确分配。 您知道在分配它们之前您不会尝试使用它们，但编译器不会。不过，我仍然推荐 reshape 方法 :)