400ms ACC Java Mergesort

• ``````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 {
ListNode helper = new ListNode(0);
ListNode helper1 = new ListNode(0);
ListNode helper2 = new ListNode(0);
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;
}

}

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;
}
}``````

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

``````public class Solution {
ListNode helper = new ListNode(0);
ListNode helper1 = new ListNode(0);
ListNode helper2 = new ListNode(0);
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;
}

}

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;
}
``````

}

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