400ms ACC Java Mergesort


  • 0
    S
    The most confusing stuff in this algorithm is that there is not a deep copy method for ListNode in Java.
    

    Thus change the object does not change the copy, but change the attribute will change the copy. This is very confusing in ListNode because the attribute is the next object.

    public class Solution {
        	public ListNode mergeList(ListNode head1, ListNode head2){
        		ListNode helper = new ListNode(0);
        		ListNode helper1 = new ListNode(0);
        		ListNode helper2 = new ListNode(0);
        		helper1 = head1;
        		helper2 = head2;
        		ListNode fakehead = helper;
        		while(helper1!=null && helper2!=null){
        			if(helper1.val>helper2.val){
        				helper.next = helper2;
        				helper2 = helper2.next;
        				helper =helper.next;
        			}else{
        				helper.next = helper1;
        				helper1 = helper1.next;
        				helper = helper.next;
        			}
        		}
        		
        		if(helper1!=null){
        			helper.next = helper1;
        		}
        		if(helper2!=null){
        			helper.next = helper2;
        		}
        		return fakehead.next;
        		
        	}
        	
        	public ListNode sortList(ListNode root){
        		int length = length(root);
        		ListNode l1 = new ListNode(0);
        		ListNode l2 = new ListNode(0);
        		ListNode res = new ListNode(0);
        		if(length>1){
        			int temp  = length/2;
        			ListNode node1 =root;
        			for(int i = 0; i<temp-1; i++){
        				node1 = node1.next;
        			}
        			ListNode node2 = node1.next;
        			node1.next= null;
        			node1 = root;
        			l1 = sortList(node1);
        			l2 = sortList(node2);
        			res = mergeList(l1, l2);
        			return res;
        		}
        		return root;
        	}
        	
        	public int length(ListNode node){
        		int i = 1;
        		if (node==null){
        			return 0;
        		}else{
        			while(node.next!=null){
        				i++;
        				node = node.next;
        			}
        		}		
        		return i;
        	}
        }

  • 0
    J

    I think length() can be delivered, so length could be counted only once!

    public class Solution {
        public ListNode mergeList(ListNode head1, ListNode head2){
            ListNode helper = new ListNode(0);
            ListNode helper1 = new ListNode(0);
            ListNode helper2 = new ListNode(0);
            helper1 = head1;
            helper2 = head2;
            ListNode fakehead = helper;
            while(helper1!=null && helper2!=null){
                if(helper1.val>helper2.val){
                    helper.next = helper2;
                    helper2 = helper2.next;
                    helper =helper.next;
                }else{
                    helper.next = helper1;
                    helper1 = helper1.next;
                    helper = helper.next;
                }
            }
    
            if(helper1!=null){
                helper.next = helper1;
            }
            if(helper2!=null){
                helper.next = helper2;
            }
            return fakehead.next;
    
        }
    
        public ListNode sortList(ListNode root){
            int len = length(root);
            if(len > 1) {
                root = sort(root, len); 
            }
            return root;
        }
        
        public ListNode sort(ListNode root, int len) {
            ListNode l1 = new ListNode(0);
            ListNode l2 = new ListNode(0);
            ListNode res = new ListNode(0);
            if(len>1){
                int temp  = len/2;
                ListNode node1 =root;
                for(int i = 0; i<temp-1; i++){
                    node1 = node1.next;
                }
                ListNode node2 = node1.next;
                node1.next= null;
                node1 = root;
                l1 = sort(node1, temp);
                l2 = sort(node2, len - temp);
                res = mergeList(l1, l2);
                return res;
            }
            return root;
        }
    
        public int length(ListNode node){
            int i = 1;
            if (node==null){
                return 0;
            }else{
                while(node.next!=null){
                    i++;
                    node = node.next;
                }
            }       
            return i;
        }
    

    }


Log in to reply
 

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