How do you solve Sort List on LeetCode?

Sort List (LeetCode #148) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(1) space complexity. Key insight: Merge Sort is efficient for linked lists due to its linear merging process.

What is the brute force solution for Sort List?

The brute force approach for Sort List is Brute Force, with O(n²) time complexity and O(n) space complexity. The simplest way to sort a linked list is to convert it to an array, sort the array, and then convert it back to a linked list. This method is straightforward but inefficient for larger lists. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Sort List?

Sort List uses the following concepts: Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort. The recommended patterns to study are: Two Pointers, Divide and Conquer, Merge Sort.

What are the interview tips for Sort List?

Explain your thought process clearly when discussing your approach. Be prepared to discuss the time and space complexities of your solution. Practice explaining the merge sort process as it's a common topic.

What are common mistakes when solving Sort List?

Not handling edge cases like empty lists or single-node lists. Confusing the merge process with sorting an array.

#148

Sort List

Medium

Linked ListTwo PointersDivide and ConquerSortingMerge SortTwo PointersDivide and ConquerMerge Sort

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(n)	O(1)

💡

Intuition

Time O(n log n)Space O(1)

Using the Merge Sort algorithm is optimal for sorting linked lists. It works in O(n log n) time and is well-suited for linked lists because it doesn't require random access to elements.

⚙️

Algorithm

3 steps

1Step 1: Find the middle of the linked list using the slow and fast pointer technique.
2Step 2: Recursively sort the left half and the right half of the list.
3Step 3: Merge the two sorted halves back together.

solution.py35 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def sortList(head):
8    if not head or not head.next:
9        return head
10    # Step 1: Find the middle of the linked list
11    slow, fast = head, head.next
12    while fast and fast.next:
13        slow = slow.next
14        fast = fast.next.next
15    mid = slow.next
16    slow.next = None
17    # Step 2: Recursively sort the halves
18    left = sortList(head)
19    right = sortList(mid)
20    # Step 3: Merge sorted halves
21    return merge(left, right)
22
23def merge(left, right):
24    dummy = ListNode(0)
25    current = dummy
26    while left and right:
27        if left.val < right.val:
28            current.next = left
29            left = left.next
30        else:
31            current.next = right
32            right = right.next
33        current = current.next
34    current.next = left if left else right
35    return dummy.next

ℹ

Complexity note: The time complexity is O(n log n) because we are dividing the list in half recursively (log n) and merging the sorted halves in linear time (n). The space complexity is O(1) if we ignore the recursion stack.

1Merge Sort is efficient for linked lists due to its linear merging process.
2Using the slow and fast pointer technique helps in finding the middle of the list efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.