题解 | #单链表的排序#

归并排序,单链表的较优实现方式

using System;
using System.Collections.Generic;

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

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

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) return head;
        int length = 0;
        ListNode pl = head;
        while (pl != null) {
            length++;
            pl = pl.next;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        for (int subLength = 1; subLength < length; subLength *= 2) {
            ListNode pre = dummy;
            ListNode cur = dummy.next;
            while (cur != null) {
                ListNode head1 = cur;
                for (int i = 1; i < subLength && cur.next != null; i++) {
                    cur = cur.next;
                }
                ListNode head2 = cur.next;
                cur.next = null;
                cur = head2;
                if (cur != null) {
                    for (int i = 1; i < subLength && cur.next != null; i++) {
                        cur = cur.next;
                    }
                }
                ListNode nextNode = null;
                if (cur != null) {
                    nextNode = cur.next;
                    cur.next = null;
                }
                pre.next = Merge(head1, head2);
                while (pre.next != null) {
                    pre = pre.next;
                }
                cur = nextNode;
            }
        }
        return dummy.next;
    }
    public ListNode Merge(ListNode head1, ListNode head2) {
        ListNode newHead = new ListNode(0);
        ListNode phead = newHead;
        while (true) {
            if (head1 == null) {
                if (head2 == null) break;
                phead.next = head2;
                break;
            }
            if (head2 == null) {
                phead.next = head1;
                break;
            }
            if (head1.val > head2.val) {
                phead.next = head2;
                head2 = head2.next;
                phead = phead.next;
            } else {
                phead.next = head1;
                head1 = head1.next;
                phead = phead.next;
            }
        }
        return newHead.next;
    }
}

快排,平均速度也是nlogn级,但是最坏情况下会有n^2的复杂度,导致超时

public class Solution {
    public ListNode SortList(ListNode head) {
        //快速排序
        ListNode phead = new ListNode(0);
        phead.next = head;
        QuickSort(phead,null);
        return phead.next;
    }
    public void QuickSort(ListNode leftpre, ListNode rightnex){
        if(leftpre.next == null) return;
        if(leftpre.next.next == rightnex) return;
        ListNode left = leftpre.next;
        ListNode slowpre = left;
        ListNode fastpre = left;
        while(fastpre.next != null && fastpre.next != rightnex){
            if(left.val > fastpre.next.val){
                if(slowpre != fastpre){
                    if(slowpre.next == fastpre){
                        ListNode fast = fastpre.next;
                        fastpre.next = fast.next;
                        fast.next = slowpre.next;
                        slowpre.next = fast;
                        fastpre = slowpre.next;
                    }
                    else{
                        //slow和fast上的节点交换位置
                        ListNode slow = slowpre.next;
                        ListNode fast = fastpre.next;
                        ListNode node = fast.next;
                        fast.next = slow.next;
                        slowpre.next = fast;
                        slow.next = node;
                        fastpre.next = slow;
                    }
                }
                slowpre = slowpre.next;
            }
            fastpre = fastpre.next;
        }
        if(left != slowpre){
            //left插入到slowpre后的位置
            ListNode slow = slowpre.next;
            leftpre.next = left.next;
            left.next = slowpre.next;
            slowpre.next = left;
            QuickSort(leftpre,slowpre.next);
            if(slowpre.next != null) QuickSort(slowpre.next,rightnex);
            return;
        }
        QuickSort(slowpre,rightnex);
        return;
    }
}

冒泡,n^2时间复杂度,会超时

public ListNode SortList(ListNode head) {
        ListNode cur;//冒泡排序
        ListNode nex;
        ListNode pre;
        ListNode right = new ListNode(0);
        if(head == null) return null;
        ListNode phead = new ListNode(0);
        phead.next = head;
        while(phead.next.next != null){
            cur = phead.next;
            nex = cur.next;
            pre = phead;
            while(nex != null){
                if(cur.val > nex.val){
                    pre.next = nex;
                    cur.next = nex.next;
                    nex.next = cur;
                    nex = cur;
                    cur = pre.next;
                }
                cur = cur.next;
                pre = pre.next;
                nex = nex.next;
            }
            pre.next = null;
            cur.next = right.next;
            right.next = cur;
        }
        phead.next.next = right.next;
        right.next = phead.next;
        return right.next;
    }

以上算法的逻辑经测试均无问题