Merge Sort in JAVA


  • 0
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public ListNode partitionList(ListNode head) {
            ListNode midNode = head;
            ListNode runnerNode = head;
            ListNode prev = null;
            while ( runnerNode != null && runnerNode.next != null ) {
                prev = midNode;
                midNode = midNode.next;
                runnerNode = runnerNode.next.next;
            }
            prev.next = null;
            return midNode;
        }
        
        public ListNode mergeTwoLists(ListNode nodeOne, ListNode nodeTwo) {
               ListNode dummyNode = new ListNode(-1);
               ListNode pointer = dummyNode;
               while ( nodeOne != null || nodeTwo != null ) {
                   if ( nodeOne == null ){
                       pointer.next = nodeTwo;
                       break;
                   }else if ( nodeTwo == null ) {
                       pointer.next = nodeOne;
                       break;
                   }
                   
                    ListNode minNode = null;
                   if ( nodeOne.val <= nodeTwo.val){
                       minNode = nodeOne;
                       nodeOne = nodeOne.next;
                   }else {
                       minNode = nodeTwo;
                       nodeTwo = nodeTwo.next;
                   }
                   pointer.next = minNode;
                   pointer = pointer.next;
                   
               }
                return dummyNode.next;
        }
        
        public ListNode mergeSort(ListNode head) {
               if ( head == null || head.next == null ) {
                   return head;
               }
               ListNode midNode = partitionList(head);
               return mergeTwoLists(mergeSort(head),mergeSort(midNode));           
        }
        
        public ListNode sortList(ListNode head) {
            return mergeSort(head);
        }
    }
    

    Do not use recursion in "mergeTwoLists()" it causes much overhead and stack over flow in such recursive code !!


  • 0

    I think it might be an issue with the above code. The return minNode in mergeTwoLists can't get the correct result. Using return dummyNode.next insteads.


  • 0

    @Tanych Edited .. I don't know how it changed but you are right !! .. thank you :D


Log in to reply
 

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