一. 题目

二. 思路

1. 归并排序-递归

2. 归并排序-迭代

三. 代码

1. 归并排序-递归

class Solution
{
    ListNode mergeSort(ListNode l, ListNode r)//返回排序后的头
    {
        if (l == r)
        {
            if (l != null) l.next = null;//最开始全部情空
            return l;
        }

        int n = 1;//当前段节点数量
        ListNode cur = l;//当前节点
        while (cur != r)//此时还没拆开
        {
            ++n;
            cur = cur.next;
        }

        cur = l;
        ListNode pn = l;//前一个节点，记录左边尾巴
        for (int i = 0; i < n / 2; ++i)//cur是右边的开头
        {
            pn = cur;
            cur = cur.next;
        }

        ListNode ls = mergeSort(l, pn);//归并
        ListNode rs = mergeSort(cur, r);

        ListNode vh = new ListNode();
        cur = vh;
        while (ls != null && rs != null)
            if (ls.val <= rs.val)
            {
                cur.next = ls;
                cur = ls;
                ls = ls.next;
            } else
            {
                cur.next = rs;
                cur = rs;
                rs = rs.next;
            }
        while (ls != null)
        {
            cur.next = ls;
            cur = ls;
            ls = ls.next;
        }

        while (rs != null)
        {
            cur.next = rs;
            cur = rs;
            rs = rs.next;
        }

        return vh.next;
    }

    public ListNode sortList(ListNode head)
    {
        ListNode tail = head;
        while (tail != null && tail.next != null) tail = tail.next;
        return mergeSort(head, tail);
    }
}

2. 归并排序-迭代

class Solution
{
    ListNode merge(ListNode h1, ListNode h2)
    {
        ListNode vh = new ListNode(), cur = vh;
        while (h1 != null && h2 != null)
        {
            if (h1.val <= h2.val)
            {
                cur.next = h1;
                h1 = h1.next;
            } else
            {
                cur.next = h2;
                h2 = h2.next;
            }
            cur = cur.next;
        }

        while (h1 != null)
        {
            cur.next = h1;
            h1 = h1.next;
            cur = cur.next;
        }

        while (h2 != null)
        {
            cur.next = h2;
            h2 = h2.next;
            cur = cur.next;
        }

        return vh.next;
    }

    public ListNode sortList(ListNode head)
    {
        int n = 0;
        for (ListNode i = head; i != null; i = i.next)
            ++n;

        ListNode vh = new ListNode();
        vh.next = head;
        for (int i = 1; i < n; i <<= 1)//长度每次为2倍
        {//前一段的尾巴和前一个遍历的节点
            ListNode ps = vh, pn = vh, cur = vh.next;
            while (cur != null)//cur是当前段的下一个节点
            {
                ListNode h1 = cur;
                for (int j = 0; j < i && cur != null; ++j)
                {
                    pn = cur;
                    cur = cur.next;
                }

                pn.next = null;
                ListNode h2 = cur;
                for (int j = 0; j < i && cur != null; ++j)
                {
                    pn = cur;
                    cur = cur.next;
                }

                pn.next = null;
                ps.next = merge(h1, h2);
                while (ps.next != null)
                    ps = ps.next;
            }
        }

        return vh.next;
    }
}