Sort a Linked List - Amazon Top Interview Questions

                        Solution in C++ :

LLNode* merge(LLNode* left, LLNode* right) {
    LLNode dummy_head;
    LLNode* curr = &dummy_head;

    while (left && right) {
        if (left->val < right->val) {
            curr->next = left;
            left = left->next;

            curr = curr->next;
            curr->next = nullptr;
        } else {
            curr->next = right;
            right = right->next;

            curr = curr->next;
            curr->next = nullptr;
        }
    }

    while (left) {
        curr->next = left;
        left = left->next;

        curr = curr->next;
        curr->next = nullptr;
    }

    while (right) {
        curr->next = right;
        right = right->next;

        curr = curr->next;
        curr->next = nullptr;
    }

    return dummy_head.next;
}

LLNode* merge_sort(LLNode* node) {
    if (!node || !node->next) return node;

    LLNode *slow = node, *fast = node, *prev = nullptr;
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    prev->next = nullptr;
    LLNode* left = merge_sort(node);
    LLNode* right = merge_sort(slow);

    return merge(left, right);
}

LLNode* solve(
    LLNode* node) {  // Merge sort takes O(N logN) time and O(log N) for recursive call stack
    return merge_sort(node);
}
                    

                        Solution in Python : 
                            
# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def solve(self, node):
        if node is None or node.next is None:
            return node
        slow, fast = node, node
        while fast is not None and fast.next is not None:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        prev.next = None
        l1 = self.solve(node)
        l2 = self.solve(slow)
        return self.mergeTwoLists(l1, l2)

    def mergeTwoLists(self, l1, l2):
        if l1 is None and l2 is not None:
            return l2
        elif l1 is not None and l2 is None:
            return l1
        elif l1 is None and l2 is None:
            return None
        t1 = l1
        prev = None  # Can add a dummy node to avoid prev=None edge case handling
        while t1 is not None and l2 is not None:
            if l2.val <= t1.val:
                if prev is None:
                    save = l2
                    l2 = l2.next
                    save.next = t1
                    l1 = save
                    prev = save
                else:
                    save = l2
                    l2 = l2.next
                    prev.next = save
                    save.next = t1
                    prev = save
            else:
                prev = t1
                t1 = t1.next
        if t1 is None and l2 is not None:
            prev.next = l2
        return l1