Why does this code fail the runtime complexity test?


  • 0
    H

    Hi, the input is {3,2,4} and it fails !

    public class Solution {
    
        public ListNode sortList(ListNode head) {
            
            int length = findLength(head);
            return mergeSort(head, length);
        }
        
        public ListNode mergeSort(ListNode head, int length) {
            
            if (length == 1 || length == 0) {
                
                return head;
                
            } else if (length == 2) {
                
                if (head.val > head.next.val) {
                    
                    swap(head, head.next);
                    
                    return head;
                    
                } else {
                    
                    return head;
                }
                
            } else {
                
                int mid = length / 2;
                
                ListNode midNode = goToPos(head, mid);
                
                int leftLength = mid;
                int rightLength = length - mid;
                
                ListNode leftHead = mergeSort(head, leftLength);
                ListNode rightHead = mergeSort(midNode, rightLength);
                
                return merge(leftHead, leftLength, rightHead, rightLength);
                
            }
        }
        
        private ListNode merge(ListNode leftHead, int leftLength, ListNode rightHead, int rightLength) {
            
            ListNode head = null;
            if (leftHead.val > rightHead.val) {
                
                head = rightHead;
                rightLength --;
                
                rightHead = rightHead.next;
                
            } else {
                
                head = leftHead;
                leftLength --;
                
                leftHead = leftHead.next;
            }
            
            ListNode node = head;
            while ((leftLength > 0) && (rightLength > 0)) {
                
                if (leftHead.val > rightHead.val) {
                
                    rightLength --;
                    
                    node.next = rightHead;
                    node = rightHead;
                    
                    rightHead = rightHead.next;
                    
                } else {
                    
                    leftLength --;
                    
                    node.next = leftHead;
                    node = leftHead;
                    
                    leftHead = leftHead.next;
                }
            }
            
            if (leftLength > 0) {
                
                while (leftLength > 0) {
                    
                    leftLength --;
                    
                    node.next = leftHead;
                    node = leftHead;
                    
                    leftHead = leftHead.next;
                }
                
            } else if (rightLength > 0) {
    
                while (leftLength > 0) {
    
                    rightLength --;
                    
                    node.next = rightHead;
                    node = rightHead;
                    
                    rightHead = rightHead.next;     
                }
            }
            
            return head;
        }
        
        private void swap(ListNode leftNode, ListNode rightNode) {
            
            int val = leftNode.val;
            
            leftNode.val = rightNode.val;
            
            rightNode.val = val;
        }
        
        private ListNode goToPos(ListNode head, int pos) {
            
            ListNode node = head;
            for (int i = 0; i < pos; i++) {
                
                node = node.next;
            }
            
            return node;
        }
        
        private int findLength(ListNode head) {
            
            int i = 0;
            while (head != null) {
                
                i++;
                head = head.next;
            }
            
            return i;
        }
    }

Log in to reply
 

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