# Java Bottom-up Iterative Merge Sort easy to understand : O(n*logn) time, O(1) space

• Here is my Java solution : bottom-up iteratively merge sort a LinkedList
Time complexity : O(n*log(n))
Space complexity : O(1); no recursion because iterative bottom-up is used; in-place because it's a LinkedList

``````public class Solution {
public ListNode sortList(ListNode head) {
// Calculate length of the list
int len = length(head);

// dummy's next node is always the updated head (min node)
ListNode dummy = new ListNode(0);
dummy.next = head;
for (int size = 1; size < len; size *= 2) {
// Head of left sub-list
ListNode head1 = dummy.next;
ListNode tail = dummy;
while (head1 != null) {
tail.next = head1;
// Head of right sub-list
ListNode head2 = moveSize(head1, size);
if (head2 != null) {
ListNode nextHead = moveSize(head2, size);
tail = merge(tail, head1, head2);
head1 = nextHead;
} else {
break;
}
}
}
return dummy.next;
}

private int length(ListNode head) {
int len = 0;
ListNode cur = head;
while (cur != null) {
cur = cur.next;
len++;
}
return len;
}

// Get the node that is size to the right of the head
private ListNode moveSize(ListNode head, int size) {
ListNode newHead = head;
for (int i = 0; i < size; i++) {
if (newHead == null)
return null;
if (i == size - 1) {
// Set tail to null
ListNode tmp = newHead.next;
newHead.next = null;
newHead = tmp;
} else {
newHead = newHead.next;
}
}
return newHead;
}

// merge two sorted linkedlist and return the new tail of merged list
private ListNode merge(ListNode tail, ListNode head1, ListNode head2) {
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
tail.next = head1;
tail = tail.next;
head1 = head1.next;
} else {
tail.next = head2;
tail = tail.next;
head2 = head2.next;
}
}
// link to the non-empty list
if (head1 == null)
tail.next = head2;
if (head2 == null)
tail.next = head1;
// move to the end
while (tail.next != null)
tail = tail.next;
return tail;
}
}
``````

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