在 O(n log n) 时间复杂度和常数级空间复杂度下, 对链表进行排序.
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->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) {
- /**
- 归并排序稳定 O(NlogN), 但是容易出错, 需要注意细节
- **/
- return sort(head);
- }
- private ListNode sort(ListNode head) {
- // 用快慢指针找出中间节点并断开, 对断开后的两个链表分别排序后再合并
- if(head == null || head.next == null) return head;
- ListNode slow = head, fast = head, mid = head;
- while(fast != null && fast.next != null) {
- mid = slow;
- slow = slow.next;
- fast = fast.next.next;
- }
- mid.next = null;
- // head 为左半部头节点, slow 为右半部头结点
- ListNode lhead = sort(head);
- ListNode rhead = sort(slow);
- return merge(lhead, rhead);
- }
- private ListNode merge(ListNode lhead, ListNode rhead) {
- ListNode head = new ListNode(0);
- ListNode cur = head;
- while(lhead != null && rhead != null) {
- if(lhead.val <= rhead.val) {
- cur.next = lhead;
- lhead = lhead.next;
- }
- else {
- cur.next = rhead;
- rhead = rhead.next;
- }
- cur = cur.next;
- }
- if(lhead != null)
- cur.next = lhead;
- if(rhead != null)
- cur.next = rhead;
- return head.next;
- }
- }
来源: http://www.bubuko.com/infodetail-3070768.html