排序链表

原题链接

使用的方法

归并排序

解题思路

• 归并排序的核心思想是分治法，将链表分成两半，分别对两半进行排序，然后再将两个有序链表合并成一个有序链表。
• 首先，使用快慢指针找到链表的中点，将链表分成两半。
• 然后，递归地对两半链表进行排序。
• 最后，使用一个辅助函数将两个有序链表合并成一个有序链表，并返回合并后的链表头节点。

代码实现

/**
 * 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) {
        if(head == null || head.next == null) return head;
        ListNode fast = head.next, slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(temp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while(left != null && right != null){
            if(left.val < right.val){
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }
}