CA 24 - Sort a Linked List using Merge Sort

Problem Statement: here

Solution:

• The linked list is not easy to sort directly because random access is not possible, so Merge Sort is chosen as it works efficiently with linked lists.
• The process begins by dividing the linked list into two halves using two pointers, where one moves one step at a time and the other moves two steps, helping to find the middle.
• Once the middle is found, the list is split into two separate smaller lists.
• This splitting process continues recursively until each part contains only one node, which is already considered sorted.
• After reaching single-node lists, the process starts combining them back together.
• During merging, the first nodes of both lists are compared, and the smaller value is linked to the result list.
• This comparison and linking continue until all nodes from both lists are merged in sorted order.
• The merging process is repeated step by step, combining larger and larger sorted lists.
• Finally, all parts are merged into one fully sorted linked list, and the head of this sorted list is returned.

def sortList(head):
    if not head or not head.next:
        return head
    # find middle
    first = head
    second = head.next
    while second and second.next:
        first = first.next
        second = second.next.next
    middle = first.next
    first.next = None
    left_part = sortList(head)
    right_part = sortList(middle)
    return merge_lists(left_part, right_part)
def merge_lists(listA, listB):
    start = ListNode(0)
    current = start
    while listA and listB:
        if listA.val < listB.val:
            current.next = listA
            listA = listA.next
        else:
            current.next = listB
            listB = listB.next
        current = current.next
    if listA:
        current.next = listA
    else:
        current.next = listB
    return start.next