recursive merge sort solution in java


  • 0
    F
    public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode slow = head, fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode right = slow.next;
            slow.next = null;
            return merge(sortList(head), sortList(right));
        }
    
        private ListNode merge(ListNode headA, ListNode headB) {
            if (headA == null) {
                return headB;
            }
            if (headB == null) {
                return headA;
            }
            if (headA.val < headB.val) {
                headA.next = merge(headA.next, headB);
                return headA;
            } else {
                headB.next = merge(headA, headB.next);
                return headB;
            }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.