Use merge sort, O(n*lg(n)), but still can't pass, ANY suggestions?

• I've checked it several times, I still think my solution meet the requirement.

The idea come from merge sort. ( bottum up way)
for length 2,4,6,8,... ------------------ ( O(lg(n)) times
we detach list 1 and list 2 from original list. --------------------- ( O(n)) times
And merge list 1 and list 2. ------------ ( O(n)) times

``````public class SortList {
// use the merge sort idea, but iteratively
// on i_th time, we use merge 2^(i-1) , nodes with another

// get the size of list
int nNodes = 0;
while (runner != null) {
nNodes++;
runner = runner.next;
}
int nInteration = (int) (Math.log(nNodes)/Math.log(2))+1;

// list in header is ascending order

for (int i = 0; i < nInteration; i++) { // log(n) times
// merge position 2^i , and the next 2^i nodes
newHeader.next = null; // reseting the new List
while (runner != null) {// run a iteration
// detach list 1
// runner would point to the last node of list 1 ( or null if
// exceed)
for (int j = 0; j < Math.pow(2, i) - 1; j++) {
if (runner.next != null) {// detach and append on
runner = runner.next;
} else {
break;
}
}
// , detach list1 from header ,and and detach list 2
runner.next = null; // make tail of list1 ( header1) point to null
// detach list 2
for (int j = 0; j < Math.pow(2, i)-1; j++) {
if (runner != null) {// detach and append on
runner = runner.next;
} else {
break;
}
}
if (runner == null) {
} else {
runner.next = null; // to make the tail of list2 pointing to
// null
}
runner = header.next; // making runner pointing to
}
}
}

ListNode tail) {
ListNode tmp;
} else {
}
tail.next = tmp;
tail = tmp;
tail.next = null;
}
} else {
}
// make tail point to the last
while (tail.next != null) {
tail = tail.next;
}
return tail;
}
}``````

• Can you explain the idea of your algorithm? You mention you do it iteratively. How?

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