本文共 1505 字，大约阅读时间需要 5 分钟。

一、题目

力扣原题：

二、归并排序

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode sortList(ListNode head) {        if (null == head) {            return null;        }        return split(head);    }    private ListNode split(ListNode node) {        if (null == node || null == node.next) {            return node;        }        // 双指针，标记链表中点        ListNode slow = node;        ListNode fast = node.next;        while (null != fast && null != fast.next) {            slow = slow.next;            fast = fast.next.next;        }        // 链表分割        ListNode pre = node;        ListNode post = slow.next;        slow.next = null;        // 递归分割        ListNode left = split(pre);        ListNode right = split(post);        return merge(left, right);    }    private ListNode merge(ListNode pre, ListNode post) {        ListNode node = new ListNode(-1);        ListNode cur = node;        while (null != pre && null != post) {            if (pre.val <= post.val) {                cur.next = new ListNode(pre.val);                pre = pre.next;            } else {                cur.next = new ListNode(post.val);                post = post.next;            }            cur = cur.next;        }        if (null != pre) {            cur.next = pre;        }        if (null != post) {            cur.next = post;        }        return node.next;    }}

• 时间复杂度：O(nlog(n))
• 空间复杂度：O(log(n))

转载地址：http://jnaii.baihongyu.com/