Sort List

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We are given a singly linked list of integers.
  • We need to sort the linked list in ascending order.

2. Analyze the problem: To solve this problem, we can use a divide and conquer approach such as Merge Sort to sort the linked list. This approach is efficient and has a time complexity of O(n log n).

3. Design an algorithm: Here is the algorithm to solve the problem using Merge Sort:

  1. If the linked list is empty or contains only one node, it is already sorted, so return the linked list.
  2. Split the linked list into two halves using the "slow and fast pointer" technique.
  3. Recursively sort the two halves by calling the sortList function on each half.
  4. Merge the sorted halves together using a merge function that merges two sorted linked lists.
  5. Return the merged sorted linked list.

4. Explain your approach: The approach involves using the Merge Sort algorithm to sort the linked list. We divide the linked list into two halves using the slow and fast pointer technique. Then, we recursively sort each half using the sortList function. Finally, we merge the sorted halves together using a merge function that merges two sorted linked lists.

5. Write clean and readable code:

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge(head1, head2):
    dummy = ListNode()
    current = dummy

    while head1 and head2:
        if head1.val <= head2.val:
            current.next = head1
            head1 = head1.next
        else:
            current.next = head2
            head2 = head2.next
        current = current.next

    if head1:
        current.next = head1
    else:
        current.next = head2

    return dummy.next

def sortList(head):
    if not head or not head.next:
        return head

    # Split the linked list into two halves
    prev, slow, fast = None, head, head
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    prev.next = None

    # Recursively sort the two halves
    left = sortList(head)
    right = sortList(slow)

    # Merge the sorted halves
    return merge(left, right)

# Test case
head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(1)
head.next.next.next = ListNode(3)
sorted_head = sortList(head)
while sorted_head:
    print(sorted_head.val, end=" ")  # Expected output: 1 2 3 4
    sorted_head = sorted_head.next

6. Test your code: Let's test the code with the given test case:

  • Test case: head = 4 -> 2 -> 1 -> 3.
    • The expected output is 1 2 3 4 because the linked list should be sorted in ascending order.

7. Optimize if necessary: The current solution already uses an efficient algorithm, Merge Sort, which has a time complexity of O(n log n). There is no further optimization needed.

8. Handle error cases: The code assumes that the input head is a valid linked list. If the input is not a valid linked list (e.g., None or has cycles), the code may produce unexpected results or raise an error.

9. Discuss complexity analysis:

  • The time complexity of the solution is O(n log n) because we are using the Merge Sort algorithm to sort the linked list. Splitting the linked list into two halves takes O(log n) time, and merging two sorted halves takes O(n) time.
  • The space complexity is O(log n) due to the recursive calls in the Merge Sort algorithm.

Next Post Previous Post