JAVA-----------Easy Version To UnderStand!!!!!


  • -1
    H
    	public static ListNode mergeSort(ListNode head1, ListNode head2) {
    	ListNode head = new ListNode(0);
    	ListNode tail = head;
    	tail.next = null;
    	ListNode p = head1, q = head2;
    	while (p != null && q != null) {
    		if (p.val <= q.val) {
    			tail.next = p;
    			tail = tail.next;
    			p = p.next;
    		} else {
    			tail.next = q;
    			tail = tail.next;
    			q = q.next;
    		}
    	}
    	if (p != null)
    		tail.next = p;
    	if (q != null)
    		tail.next = q;
    	return head.next;
    }
    
    public static ListNode getMiddleLode(ListNode head) {
    	ListNode fast = head, slow = head;
    	while (fast.next != null && fast.next.next != null) {
    		fast = fast.next.next;
    		slow = slow.next;
    	}
    	return slow;
    }
    
    public static ListNode sortList(ListNode head) {
    	if (head == null || head.next == null)
    		return head;
    	ListNode midLode = getMiddleLode(head);
    	ListNode second = midLode.next;
    	midLode.next = null;
    	ListNode first = head;
    	first = sortList(first);
    	second = sortList(second);
    	head = mergeSort(first, second);
    	return head;
    }

Log in to reply
 

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