从 Java 的 LinkedList 类获取"sub-LinkedLlists"(用于 MergeSort 目的)

Question

我正在尝试在java的标准LinkedList上练习MergeSort算法。我是标准库的新手。

我遇到的问题是创建"子链接列表"以从合并排序中获得最佳性能。

我有一个工作代码，但不幸的是，它将LinkedList视为某个数组：

public void mergeSort(LinkedList<Integer> lisst) {
if (lisst.size() < 2){
return;
}    
int middleindex  = lisst.size()/2;    
LinkedList<Integer> LeftList = new LinkedList<Integer>();

for(int i = 0; i< middleindex; i++){    
LeftList.addLast(lisst.get(i));
}
mergeSort(LeftList);
LinkedList<Integer> RightList = new LinkedList<Integer>();
for (int i = middleindex; i< lisst.size(); i++){    
RightList.addLast(lisst.get(i));    
}
mergeSort(RightList);
SortedMerge(RightList,LeftList,lisst);    
}

从我所读的内容来看，这样做会扼杀在链接列表上合并排序的目的。但是，如何实际获取具有标准 LinkedList 类对象的子链表呢？如果我是用这样的节点类编写的，我可以自信地做到这一点：

node leftHead = lisst.get(middleindex);
mergeSort(lefthead);// Assuming the method also takes a node instead of LL

但是阅读库，我不知道如何指向中间元素并将其余元素用作子列表，而无需循环将其添加到新的链表

有没有一种非常简单的方法可以做到这一点？ 我没有看到 sth 吗？

谢谢。

Answer 1

如果你只想要LinkedList的正确部分，你应该有以下内容：

public static <T> LinkedList<T> removeUntil(LinkedList<T> list, int index) {
for (int i = 0; i < index; i++) {
list.removeFirst();
}
return list;
}

用例

public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>(Arrays.asList(new Integer[] {1, 3, 5, 6, 9}));
System.out.format("Input : %s%n", list);
list = removeUntil(list, 3);
System.out.format("Output: %s%n", list);
}

用例输出

Input : [1, 3, 5, 6, 9]
Output: [6, 9]

---

如果您希望保留LinkedList的左侧部分，您应该拥有以下内容：

public static <T> LinkedList<T>[] split(LinkedList<T> list, int index) {
LinkedList<T> left = new LinkedList<>();
for (int i = 0; i < index; i++) {
T t = list.removeFirst();
left.addLast(t);
}
return new LinkedList[] {
left, list
};
}

用例

public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>(Arrays.asList(new Integer[] {1, 3, 5, 6, 9}));
System.out.format("Input : %s%n", list);
LinkedList[] alist = split(list, 3);
System.out.format("Output: %s, %s%n", alist[0], alist[1]);
}

用例输出

Input : [1, 3, 5, 6, 9]
Output: [1, 3, 5], [6, 9]

参考：

• LinkedList (Java Platform SE 8 API Reference(