时间戳

首页 > 解决方案 > 在原位链表上实现自然归并排序，并且只交换来自节点的项目

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

问题描述

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

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

我知道在合并之前保持两个子列表的顺序是关键，但我找不到解决方法。

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

private class Node {
    Item item;
    Node next;

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

标签： javaalgorithmsortinglinked-listmergesort

解决方案

如需灵感，请查看 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登陆的节点。为简洁起见，省略了退出递归。

推荐阅读