题解 | #单链表的排序#快慢指针归并排序

解法：归并排序

归并排序需要将链表分成长度均等的左右两部分，分别对两部分进行排序之后再合并

如何把两个链表分成长度均等的两部分？ 快慢指针

import java.util.*;

public class Solution {
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // only 2 nodes
        if (head.next.next == null) {
            if (head.next.val < head.val) {
                int temporary = head.next.val;
                head.next.val = head.val;
                head.val = temporary;
            }
            return head;
        }
        // find middle
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode middle = slow.next;
        // break down linked list into two part
        slow.next = null;
        return merge(sortInList(head), sortInList(middle));
    }

    private ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        ListNode previousOfHead = new ListNode(-1000000001);
        ListNode current = previousOfHead;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                current.next = head1;
                head1 = head1.next;
            } else {
                current.next = head2;
                head2 = head2.next;
            }
            current = current.next;
        }
        if (head1 != null) {
            current.next = head1;
        } else {
            current.next = head2;
        }
        return previousOfHead.next;
    }
}