Jobs

Interviews

Discussions

Sort List #171 Most Asked

Medium

TikTok

5 views

Topics:

Linked Lists

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is in the range [0, 5 * 10⁴].
-10⁵ <= Node.val <= 10⁵

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Try coding it in LeetCode

Sort List #171 Most Asked

Medium

TikTok

5 views

Topics:

Linked Lists

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is in the range [0, 5 * 10⁴].
-10⁵ <= Node.val <= 10⁵

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the elements in the list, and what is the range of possible values (e.g., integers, floats, strings)?
Can the list be empty or null? If so, what should I return?
Are there any duplicate values in the list, and if so, how should they be handled in the sorted output (e.g., should they be preserved)?
What type of list is this (singly linked list, doubly linked list, array-based list), and how is it represented in memory?
Are we aiming for a specific sorting algorithm (e.g., in-place sort, merge sort with O(n log n) time complexity, etc.) or are we free to choose the most appropriate one?

Brute Force Solution

Approach

The brute force approach to sorting is like trying every single possible order of the items you want to sort. We check each of these orders to see if it is correctly sorted. If not, we move to the next possibility until a sorted order is found.

Here's how the algorithm would work step-by-step:

Imagine you can rearrange the items in any order you like.
Pick a possible order of all the items.
Check if the items are now in the correct sorted order.
If they are, you're done!
If not, pick a different possible order.
Keep doing this until you find an order where the items are correctly sorted.

Code Implementation

import itertools

def is_sorted(possible_permutation):
    for i in range(len(possible_permutation) - 1):
        if possible_permutation[i] > possible_permutation[i + 1]:
            return False
    return True

def sort_list_brute_force(input_list):
    # Generate all possible permutations of the input list.
    all_permutations = itertools.permutations(input_list)

    for possible_permutation in all_permutations:
        # Check if current permutation is sorted.

        if is_sorted(possible_permutation):

            # If sorted, return the sorted permutation as a list.
            return list(possible_permutation)

    # If no sorted permutation is found, return the original list (should not happen).
    return input_list

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach, as described, involves generating all possible permutations of the input list of size 'n'. Generating all permutations takes O(n!) time. For each of these permutations, we must check if it is sorted, which requires iterating through all 'n' elements in the list. Therefore, the overall time complexity is O(n! * n), where n! accounts for generating all permutations, and n accounts for checking if a given permutation is sorted.

Space Complexity

O(N!) – The provided brute force algorithm considers every possible permutation of the input list. To generate these permutations, it implicitly uses a data structure to store the current permutation being checked. In the worst-case scenario, the algorithm might need to explore all N! (N factorial) possible permutations before finding the correct sorted order. Therefore, the algorithm uses space proportional to the number of permutations it has to hold in memory, leading to a space complexity of O(N!).

Optimal Solution

Approach

To efficiently sort a linked list, we can apply the divide-and-conquer strategy. This means repeatedly splitting the list into smaller sublists, sorting each sublist, and then merging them back together in sorted order. This approach avoids unnecessary comparisons and rearrangements, resulting in faster performance.

Here's how the algorithm would work step-by-step:

First, divide the unsorted list into smaller sublists until each sublist contains only one element. A list with one element is inherently sorted.
Next, repeatedly merge the sublists to produce new sorted sublists. This merging process compares elements from the two sublists being merged and places the smaller element into the new sorted sublist.
Keep merging the sorted sublists until there is only one sorted list remaining. This final list is the sorted version of the original unsorted list.

Code Implementation

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

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

    # Function to find the middle of the linked list
    def get_middle(head_node):
        slow_pointer = head_node
        fast_pointer = head_node.next

        while fast_pointer and fast_pointer.next:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next

        return slow_pointer

    # Function to merge two sorted linked lists
    def merge(list_one, list_two):
        dummy_node = ListNode()
        tail = dummy_node

        while list_one and list_two:
            if list_one.val < list_two.val:
                tail.next = list_one
                list_one = list_one.next
            else:
                tail.next = list_two
                list_two = list_two.next
            tail = tail.next

        if list_one:
            tail.next = list_one
        elif list_two:
            tail.next = list_two

        return dummy_node.next

    middle = get_middle(head)
    head_next = middle.next
    middle.next = None

    # Recursively sort both halves
    left_side = sort_list(head)
    right_side = sort_list(head_next)

    # Merging the two sorted sublists
    sorted_list = merge(left_side, right_side)

    return sorted_list

#Test
# Create a linked list: 4 -> 2 -> 1 -> 3
head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(1)
head.next.next.next = ListNode(3)

# Sort the linked list
sorted_head = sort_list(head)

# Print the sorted linked list
#while sorted_head:
#    print(sorted_head.val, end=" " )
#    sorted_head = sorted_head.next

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm uses a divide and conquer approach similar to merge sort. Dividing the linked list into sublists of size one takes O(log n) time since we repeatedly halve the list. Merging the sublists back together, comparing and placing elements into the correct order, takes O(n) time for each level of merging. Therefore, the overall time complexity is O(n log n).

Space Complexity

O(log N) – The divide and conquer approach, specifically merge sort, as described involves recursive calls to split the list. In the worst-case scenario, the recursion depth is logarithmic with respect to the number of nodes in the list (N), where N is the number of elements in the original linked list. Each recursive call adds a new frame to the call stack, thus the auxiliary space used by the call stack is proportional to the recursion depth. Therefore, the space complexity is O(log N).

Edge Cases

Case	How to Handle
Null or empty list input	Return null or an empty list immediately to avoid NullPointerExceptions or unnecessary processing.
List with only one element	Return the original list as it is already sorted.
List with two elements, already sorted	Handle this case correctly by comparing the two elements and returning them in the same order.
List with two elements, reverse sorted	Swap the elements to achieve correct sorting and return the new list.
List with all identical elements	Ensure the sorting algorithm handles this without infinite loops or stack overflows; quicksort is known to have quadratic complexity with all equal elements.
List with a large number of elements exceeding memory limits (consider external sorting)	If the dataset is too large, use an external merge sort that sorts chunks of data and merges the sorted chunks.
List containing negative numbers, positive numbers and zero	The sorting algorithm should handle mixed signs correctly as integers can be compared directly.
List with integer overflow if summing during comparison	Use subtraction for comparisons to avoid overflow, e.g., a < b is better expressed as a - b < 0.

Null or empty list input

How to Handle:

Return null or an empty list immediately to avoid NullPointerExceptions or unnecessary processing.

List with only one element

How to Handle:

Return the original list as it is already sorted.

List with two elements, already sorted

How to Handle:

Handle this case correctly by comparing the two elements and returning them in the same order.

List with two elements, reverse sorted

How to Handle:

Swap the elements to achieve correct sorting and return the new list.

List with all identical elements

How to Handle:

Ensure the sorting algorithm handles this without infinite loops or stack overflows; quicksort is known to have quadratic complexity with all equal elements.

List with a large number of elements exceeding memory limits (consider external sorting)

How to Handle:

If the dataset is too large, use an external merge sort that sorts chunks of data and merges the sorted chunks.

List containing negative numbers, positive numbers and zero

How to Handle:

The sorting algorithm should handle mixed signs correctly as integers can be compared directly.

List with integer overflow if summing during comparison

How to Handle:

Use subtraction for comparisons to avoid overflow, e.g., a < b is better expressed as a - b < 0.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the elements in the list, and what is the range of possible values (e.g., integers, floats, strings)?
Can the list be empty or null? If so, what should I return?
Are there any duplicate values in the list, and if so, how should they be handled in the sorted output (e.g., should they be preserved)?
What type of list is this (singly linked list, doubly linked list, array-based list), and how is it represented in memory?
Are we aiming for a specific sorting algorithm (e.g., in-place sort, merge sort with O(n log n) time complexity, etc.) or are we free to choose the most appropriate one?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you can rearrange the items in any order you like.
Pick a possible order of all the items.
Check if the items are now in the correct sorted order.
If they are, you're done!
If not, pick a different possible order.
Keep doing this until you find an order where the items are correctly sorted.

Code Implementation

import itertools

def is_sorted(possible_permutation):
    for i in range(len(possible_permutation) - 1):
        if possible_permutation[i] > possible_permutation[i + 1]:
            return False
    return True

def sort_list_brute_force(input_list):
    # Generate all possible permutations of the input list.
    all_permutations = itertools.permutations(input_list)

    for possible_permutation in all_permutations:
        # Check if current permutation is sorted.

        if is_sorted(possible_permutation):

            # If sorted, return the sorted permutation as a list.
            return list(possible_permutation)

    # If no sorted permutation is found, return the original list (should not happen).
    return input_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, divide the unsorted list into smaller sublists until each sublist contains only one element. A list with one element is inherently sorted.
Next, repeatedly merge the sublists to produce new sorted sublists. This merging process compares elements from the two sublists being merged and places the smaller element into the new sorted sublist.
Keep merging the sorted sublists until there is only one sorted list remaining. This final list is the sorted version of the original unsorted list.

Code Implementation

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

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

    # Function to find the middle of the linked list
    def get_middle(head_node):
        slow_pointer = head_node
        fast_pointer = head_node.next

        while fast_pointer and fast_pointer.next:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next

        return slow_pointer

    # Function to merge two sorted linked lists
    def merge(list_one, list_two):
        dummy_node = ListNode()
        tail = dummy_node

        while list_one and list_two:
            if list_one.val < list_two.val:
                tail.next = list_one
                list_one = list_one.next
            else:
                tail.next = list_two
                list_two = list_two.next
            tail = tail.next

        if list_one:
            tail.next = list_one
        elif list_two:
            tail.next = list_two

        return dummy_node.next

    middle = get_middle(head)
    head_next = middle.next
    middle.next = None

    # Recursively sort both halves
    left_side = sort_list(head)
    right_side = sort_list(head_next)

    # Merging the two sorted sublists
    sorted_list = merge(left_side, right_side)

    return sorted_list

#Test
# Create a linked list: 4 -> 2 -> 1 -> 3
head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(1)
head.next.next.next = ListNode(3)

# Sort the linked list
sorted_head = sort_list(head)

# Print the sorted linked list
#while sorted_head:
#    print(sorted_head.val, end=" " )
#    sorted_head = sorted_head.next

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty list input	Return null or an empty list immediately to avoid NullPointerExceptions or unnecessary processing.
List with only one element	Return the original list as it is already sorted.
List with two elements, already sorted	Handle this case correctly by comparing the two elements and returning them in the same order.
List with two elements, reverse sorted	Swap the elements to achieve correct sorting and return the new list.
List with all identical elements	Ensure the sorting algorithm handles this without infinite loops or stack overflows; quicksort is known to have quadratic complexity with all equal elements.
List with a large number of elements exceeding memory limits (consider external sorting)	If the dataset is too large, use an external merge sort that sorts chunks of data and merges the sorted chunks.
List containing negative numbers, positive numbers and zero	The sorting algorithm should handle mixed signs correctly as integers can be compared directly.
List with integer overflow if summing during comparison	Use subtraction for comparisons to avoid overflow, e.g., a < b is better expressed as a - b < 0.

Null or empty list input

How to Handle:

Return null or an empty list immediately to avoid NullPointerExceptions or unnecessary processing.

List with only one element

How to Handle:

Return the original list as it is already sorted.

List with two elements, already sorted

How to Handle:

Handle this case correctly by comparing the two elements and returning them in the same order.

List with two elements, reverse sorted

How to Handle:

Swap the elements to achieve correct sorting and return the new list.

List with all identical elements

How to Handle:

Ensure the sorting algorithm handles this without infinite loops or stack overflows; quicksort is known to have quadratic complexity with all equal elements.

List with a large number of elements exceeding memory limits (consider external sorting)

How to Handle:

If the dataset is too large, use an external merge sort that sorts chunks of data and merges the sorted chunks.

List containing negative numbers, positive numbers and zero

How to Handle:

The sorting algorithm should handle mixed signs correctly as integers can be compared directly.

List with integer overflow if summing during comparison

How to Handle:

Use subtraction for comparisons to avoid overflow, e.g., a < b is better expressed as a - b < 0.

0/0 TikTok questions completed

0/0 completed