归并排序链表

LeetCode 148

原题链接

归并排序

分治思想，链表对半分，一直对半分，直到分成两两的链表节点，然后两两排序，再归并回去，最终结果就是有序的链表。

这里存在几个问题：

1. 怎么找到链表的中点
2. 怎么一直对半分下去，直到分成两两节点
3. 怎么合并两个链表

回答：

1. 找链表中点有一个思想，利用快慢指针，快指针走两步，慢指针走一步，这样快指针走到链表最末尾时，慢指针就正好在链表中间，接下来，应该把链表从中间切断，只需要将中间节点的next = null即可。然后开始归并排序。
2. 一直对半分下去，可以用递归的思想，实现。
3. merge函数来合并，可以参考21. 合并两个有序链表对已经排序好的链表进行连接，其中，排序的过程应该放到merge函数里，在连接之前就进行排序，然后再连接返回。

代码如下

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode sortList(ListNode head) {
        return head == null ? null : mergeSort(head);
    }
    
    private ListNode mergeSort(ListNode head) {
        if (head.next == null) {
            return head;
        }
        // p，q分别为慢指针，快指针，pre指针是来保存最后慢指针指向的中间节点，便于后面断链
        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) {
        // dummy头结点，作为待返回节点的哨兵头结点，便于后面的返回
        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;
    }
}