algorithm - 如何按其值对 ListNode(链接)进行排序？

Question

如何在不使用任何库的情况下按值对节点列表进行排序。

例子: * 输入:3->1->5->4->2 * 输出:1->2->3->4->5

列表节点.java

import java.util.List;

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int x) {
        val = x;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

排序链接列表.java

public class SortLinkList {

    public static ListNode sortLinkList(ListNode list) {
        //TODO:
        return list;
    }

}```

Answer 1

如果你想要就地排序，你可以只实现冒泡排序:

伪代码:

bool notDone = true
while(notDone)
{
    notDone = false;
    cur = head;

    while(cur.nxt != null)
    {
        prev = cur;
        cur = cur.nxt;

        if(cur.val > cur.nxt.val)
        {
            prev.nxt = cur.nxt;
            temp = cur.nxt.nxt;
            cur.nxt.nxt = cur;
            cur.nxt = temp;
            notDone = true;
        }
    }
}