1.问题重述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3 输出: 1->2->3->4 示例 2:

输入: -1->5->3->4->0 输出: -1->0->3->4->5

2.问题分析

实质就是上课讲过的链表版的归并排序，这回还是一样的用Java写（说白了就是今天摸鱼了）

3.代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode sortList(ListNode head) { return head == null ? null : mergeSort(head); } private ListNode mergeSort(ListNode head) { if (head.next == null) { return head; } ListNode p = head, q = head, pre = null; while (q != null && q.next != null) { pre = p; p = p.next; q = q.next.next; } pre.next = null; ListNode l = mergeSort(head); ListNode r = mergeSort(p); return merge(l, r); } ListNode merge(ListNode l, ListNode r) { ListNode dummyHead = new ListNode(0); ListNode cur = dummyHead; while (l != null && r != null) { if (l.val <= r.val) { cur.next = l; cur = cur.next; l = l.next; } else { cur.next = r; cur = cur.next; r = r.next; } } if (l != null) { cur.next = l; } if (r != null) { cur.next = r; } return dummyHead.next; } }

4.结果