LeetCode : 148. Sort List 排序链表-蒲公英云

LeetCode : 148. Sort List 排序链表

试题
Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

代码
回顾nlog(n)的数组排序算法，一个关键点就是找到中点。在链表中我们需要使用快慢指针来解决。
归并算法如下：

/**
 * 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(head==null || head.next==null) return head;
//         获取中节点，并将链表拆分成两部分
        ListNode mid = getMid(head);
//         合并两链表
        return mergeLists(sortList(head),sortList(mid));
    }
    public ListNode getMid(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        ListNode tail = head;
        while(fast!=null && fast.next!=null){
            tail = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        tail.next = null;
        return slow;
    }
    public ListNode mergeLists(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1!=null){
            cur.next = l1;
        }
        if(l2!=null){
            cur.next = l2;
        }
        return dummy.next;
    }
}