[leetcode] Sort List

Too much hustle for writing a non-recursion solution. So recursion.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode sortList(ListNode head) { if (head == null||head.next == null) return head; ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } ListNode mid = slow.next; slow.next = null; ListNode l1 = sortList(head); ListNode l2 = sortList(mid); return merge(l1, l2); } private ListNode merge(ListNode n1, ListNode n2){ if (n1 == null) return n2; if (n2 == null) return n1; ListNode dummy = new ListNode(-1); ListNode prev = dummy; while (n1 != null && n2 != null){ if (n1.val < n2.val){ prev.next = n1; n1 = n1.next; }else{ prev.next = n2; n2 = n2.next; } prev = prev.next; } if (n1 != null){ prev.next = n1; }else if (n2 != null){ prev.next = n2; } return dummy.next; } }