递归法
参考代码
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 tmp = slow.next; slow.next = null;//截断操作 ListNode left = sortList(head);//操作两个返回的头节点,d ListNode right = sortList(tmp); 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;//返回虚拟头节点的下一个 } }