# My bottom-up merge sort, I think it's too much for a interview.

• ``````class Solution {
private:
ListNode* merge(ListNode* slow, ListNode* fast) {
ListNode dummy(0);
ListNode* curr = &dummy;

while (slow != NULL && fast != NULL) {
if (slow->val <= fast->val) {
curr->next = slow;
curr = slow;
slow = slow->next;
} else {
curr->next = fast;
curr = fast;
fast = fast->next;
}
}
if (slow != NULL) {
curr->next = slow;
}
if (fast != NULL) {
curr->next = fast;
}
return dummy.next;
}

ListNode* getListTail(ListNode* node, int k) {
for (int i = 0; node->next != NULL && i < k; ++i) {
node = node->next;
}
return node;
}

public:
int len = 1;
bool merged = true;
while (merged) {
ListNode* mergedList = NULL;
ListNode* prevTail = NULL;

merged = false;

while (nextPair != NULL) {
ListNode* secondList = nextPair, *firstList = nextPair;
ListNode* tail;

// find the tail of the first list to merge.
tail = getListTail(firstList, len - 1);
if (tail->next != NULL) {
secondList = tail->next;
tail->next = NULL;

// find the tail of the second list
tail = getListTail(secondList, len - 1);

nextPair = tail->next;
tail->next = NULL;

merged = true;

mergedList = merge(firstList, secondList);
} else {
mergedList = firstList;
nextPair = NULL;
}

if (prevTail != NULL) {
prevTail->next = mergedList;
} else {
prevTail = mergedList;
}

while (prevTail->next != NULL) {
prevTail = prevTail->next;
}
}