题目要求实现链表的自然排序

即我们需要找出链表中的两个有序链表段，lo, mid, hi

其中lo..mid是有序的，mid+1..hi也是有序的。将两个有序段排序，并继续向后查找第三个有序段，依此类推，类似2.2.16题。

为了方便起见，我定义了一个LoMidHi类，它包含lo, mid, hi三个属性。

要归并排序链表，经过思索，i最初指向lo, j指向mid.next，i > mid或j > hi时，排序完成。

merge方法如下：

/// 归并排序，会将正确设置下一次归并排序的r.mid
private static void merge(ListNode list, LoMidHi r)
{
    NodeStr i = r.lo;
    NodeStr j = r.mid.getNext();
    NodeStr prev_i = null;
    NodeStr prev_j = r.mid;
    NodeStr nextJ = r.hi.getNext();

    // 对于是否排序完成，i > mid 或 j > r.hi

    boolean is_end = false;
    while (!is_end)
    {
        // 当j小于i的值时，
        if (less(j.getItem(), i.getItem()))
        {
            // 将j插入到i之前
            if (prev_i != null)
            {
                prev_i.setNext(j);
            }
            else
            {
                r.lo = j;
                list.setFirst(j);
            }

            // 记录j的下一个指向的元素
            // 将prev_j(r.mid)指向j的下一个元素，将j插入到i之前，并设置它们前后的引用
            prev_j.setNext(j.getNext());
            j.setNext(i);
            prev_i = j;

            // 移动j的值，其实prev_j不会改变，
            // 因为i之前和j之后的都是有序的
            j = prev_j.getNext();

            // 当j超出hi界限后，代表我们的j是移动过的，
            // 且mid+1..hi的一定都移动到了mid+1之前,所以我们的r.mid不变
            // 我们将r.hi指向r.mid
            // 这里已经完全排序，我们要跳出循环
            if (j == nextJ)
            {
                is_end = true;
                r.hi = r.mid;
            }
        }
        else
        {
            prev_i = i;
            i = i.getNext();

            // 当i > mid时，因为mid+1..hi都是有序的
            // 所以此时全部排序完成，将r.mid设置为r.hi
            if (prev_i == r.mid)
            {
                r.mid = r.hi;
                is_end = true;
            }
        }
    }
}

sort方法：

private static void sort(ListNode list)
{
    LoMidHi r = fillLoMidHi(list);
    while (r.mid != r.hi)
    {
        merge(list, r);
        NodeStr next = r.mid.getNext();
        if (next != null)
        {
            while (next.getNext() != null)
            {
                if (less(next.getItem(), next.getNext().getItem()))
                {
                    next = next.getNext();
                }
                else
                {
                    break;
                }
            }
            r.hi = next;
        }
        else
        {
            break;
        }
    }

    StdOut.println();
}