java - 就地在链表上实现自然归并排序，并且只交换来自节点的项目

Question

我必须在链表上实现自然合并排序(这很容易)，但我无法更改节点的“下一个”属性，只能交换它们具有的值。我也不能倒退，因为节点没有“prev”属性。 (链接列表没有随机访问)而且我无法创建新节点。

我只需要一些关于合并功能应该如何的提示。

我知道在我将两个子列表合并之前保持它们的顺序是关键，但我找不到办法做到这一点。

这是节点类。他们保存了一个通用的Item和下一个节点的地址

private class Node {
    Item item;
    Node next;

    public String toString() {
        if (next == null) return "[" + item + "]" + "->" + "null";
        return "[" + item + "]" + "->" + next.item + ", ";
    }
}

Answer 1

要获得灵感，请查看 STL 的 inplace_sort 实现。该算法的核心部分是巧妙的旋转。当然，它需要向后遍历，这可以通过递归实现。

简而言之，合并部分是沿着

    merge (begin, mid, end)
        left_mid = middle(begin, mid)
        right_mid = lower_bound(left_mid.value, mid, end)
        pivot = rotate(left_mid, mid, right_mid)
        merge(left, left_mid, pivot)
        merge(pivot, right_mid, end)

pivot 是初始 begin 所在的节点。为简洁起见，省略了递归。