我需要编写一个方法,该方法以单个链接的整数列表和一个称为拆分值的特殊值开头 . 列表的元素没有特定的顺序 . 该方法将节点划分为两个链接列表:一个包含所有包含小于拆分值的元素的节点,另一个包含所有其他节点 . 如果原始链表具有任何重复的整数(即,其中具有相同元素的任何两个或更多个节点),则具有该元素的新链表应具有重复该元素的相同数量的节点 . 该方法返回两个头引用 - 每个引用创建一个链接列表 .
我花了无数个小时试图做到这一点,并认为这是最接近但我编译时我的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;
}
2 回答
通过使用单个类(
IntNode
)建模列表,我认为你使它变得比它需要的更复杂 . 如果您将其建模为"the list"和"a node in the list",那么很容易有一个空列表 . 你也很简单:创建两个空列表,一个用于"lower",另一个用于"not lower"
迭代原始列表:
确定要添加元素的列表
添加元素
返回两个列表(例如,使用已完成的数组)
请注意,即使没有它,只需使用
null
表示"I haven't got this list yet"即可使代码更简单 . 目前您的代码无法编译,因为copyHeadLess
等在使用时并未明确分配 . You 知道你赢了't try to use them until they'已被分配,但编译器没有't. I'仍然建议重建方法虽然:)如果source不为null,但source.link为null(list仅由一个元素组成),那么您永远不会为copyHeadLess等分配变量 . 尝试将它们初始化为null或默认值为: