力扣hot100 排序链表 归并排序 递归

Problem: 148. 排序链表

👩?🏫 参考

💖 归并排序（递归）

? 时间复杂度: $O(n)$
🌎 空间复杂度: $O(n)$

/**
 * 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;
		ListNode slow = head;
		while (fast != null && fast.next != null)
		{
			slow = slow.next;
			fast = fast.next.next;
		}
		ListNode second = slow.next;
		slow.next = null;// 断开前后两段的联系
		ListNode left = sortList(head);
		ListNode right = sortList(second);
		ListNode h = new ListNode(0);
		ListNode dummy = 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 dummy.next;
	}
}