排序链表

这道题目的要求是对一个无序的链表进行排序，对于这个问题，我们想到的一种方法就是去模拟归并排序的过程。

但是，也就是说我们要把链表一分为二，这里就要使用我们之前学到的找到链表的中间结点的那个方法了，也就是快慢双指针，然后从中间把链表给断开，这样一分为二，也就是模拟了归并排序的过程。

合并两个链表

首先是给定两个链表，怎么把它进行合并

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


private ListNode mergeTwoLists(ListNode a, ListNode b) {
    ListNode curA = a;
    ListNode curB = b;
    ListNode head = new ListNode(0);
    ListNode tail = head;
    while (curA != null && curB != null) {
        if (curA.val < curB.val) {
            tail.next = curA;
            curA = curA.next;
        } else {
            tail.next = curB;
            curB = curB.next;
        }
        tail = tail.next;
    }
    tail.next = curA == null ? curB : curA;
    return head.next;
}

归并排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public ListNode sortList(ListNode head) {
    if 
    ListNode slow = head;
    ListNode fast = head;
    while (slow != null && fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // slow指向的就是当前链表的中间结点
    ListNode temp = slow.next;
    // 断开
    slow.next = null;
    ListNode left = sortList(head);
    ListNode right = sortList(temp);
    return mergeTwoLists(left, right);
}