JavaScript merge-sort solution. Accepted! But want to optimize it. Please suggest.


  • 0
    D
    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var sortList = function(head) {
        
        
        var mergeSort = function(head, tail) {
    
          let length = getLength(head, tail);
          if(length < 2){
            return [head, tail];
          }
          
          let mid = parseInt(length / 2);
          let leftArr = slice(0, mid, head);
          let rightArr = slice(mid, length, head);
          
          return merge(mergeSort(leftArr[0], leftArr[1]), 
                      mergeSort(rightArr[0], rightArr[1]));
        
        };
      
    
        function merge(leftArr, rightArr){
          
          let result = [];
          let leftLength = getLength(leftArr[0], leftArr[1]);
          let rightLength = getLength(rightArr[0], rightArr[1]);
          let leftIndex = 0; let rightIndex = 0;
          
          let resultHead = null; let resultTail = null; let resultPrev = null;
          
          while(leftIndex < leftLength && rightIndex < rightLength){
                
            if(leftArr[0].val < rightArr[0].val){
              result.push(leftArr[0].val);
              
              if(!resultHead){
                resultHead = new ListNode(leftArr[0].val);
                resultTail = resultHead;
              } else {
                  resultPrev = resultTail;
                  resultTail = new ListNode(leftArr[0].val);
                  resultPrev.next = resultTail;
              }
              
              leftArr[0] = leftArr[0].next;
              leftIndex++;
                
              
            } else {
              result.push(rightArr[0].val);
              
              if(!resultHead){
                resultHead = new ListNode(rightArr[0].val);
                resultTail = resultHead;
              } else {
                  resultPrev = resultTail;
                resultTail = new ListNode(rightArr[0].val);
                  resultPrev.next = resultTail;
              }
              
              
              rightArr[0] = rightArr[0].next;
              rightIndex++;
            }
          }
          
          while(leftIndex < leftLength){
            result.push(leftArr[0].val);
            
              if(!resultHead){
                resultHead = new ListNode(leftArr[0].val);
                resultTail = resultHead;
              } else {
                  resultPrev = resultTail;
                resultTail = new ListNode(leftArr[0].val);
                  resultPrev.next = resultTail;
              }
            
            
            leftArr[0] = leftArr[0].next;
            leftIndex++;
          }
          
          while(rightIndex < rightLength){
            result.push(rightArr[0].val);
           
            
              if(!resultHead){
                resultHead = new ListNode(rightArr[0].val);
                resultTail = resultHead;
              } else {
                  resultPrev = resultTail;
                resultTail = new ListNode(rightArr[0].val);
                  resultPrev.next = resultTail;
              }
            
            
            rightArr[0] = rightArr[0].next;
            rightIndex++;
          }
          
        
          return [resultHead, resultTail];
          
        }
    
        function getTail(head){
          while(head.next != null){
            head = head.next;
          }
          
          return head;
        }
        
        function getLength(head, tail){
          let length = 0;
          if(head){
              length++;
          }
          
          while(head !== tail){
            length++;
            head = head.next;
          }
          
          return length;
        }
            
            
        function slice(i, j, head){
          let k = 0;
          let newTail = null
          let newHead = null;
          while(k < i){
            head = head.next;
            k++;
          }
          newHead = head;
          
          while(k < j - 1){
            head = head.next;
            k++;
          }
          newTail = head;
          
          return [newHead, newTail];
        }
        
        
        if(!head){
            return head;
        }
        
        
        let tail = getTail(head);
        let result = mergeSort(head, tail);
      
        //display(result[0]);
        
        return result[0];
        
    };
    
    
    

Log in to reply
 

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