Transform linked list to sorted array

Question

Given a linked list, write a function to transform it into a sorted array. The linked list may contain integers in any order, and your output should be an array of these integers sorted in ascending order. Ensure that your solution maintains a time complexity of O(n log n) or better.

Codemia · Accepted Answer

To transform a linked list into a sorted array, we can identify that the primary challenges include accessing the linked list elements and ensuring the sorting is performed efficiently. Given that the linked list can contain integers in any order, we need an approach that allows us to traverse all elements and sort them. A suitable pattern for this task is to use an array as the intermediary data structure since arrays provide efficient access and sorting capabilities. We'll also ensure the overall time complexity remains O(n log n) or better, which can be achieved using a sorting algorithm like Timsort (used in Python's built-in sort).

1. **Traverse the Linked List**: Initialize an empty list to hold the elements of the linked list. Use a pointer to traverse through the linked list and append each element to the list until the end of the linked list is reached. 
   - Example: For the linked list [3 -> 1 -> 4 -> 2], we will create a list `[3, 1, 4, 2]`. 
2. **Sort the Array**: Use Python's built-in `sort()` method to sort the array in ascending order. 
   - Example: Sorting the list `[3, 1, 4, 2]` will yield `[1, 2, 3, 4]`. 
3. **Return the Sorted Array**: Finally, return the sorted array.

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

def linked_list_to_sorted_array(head):
    # Step 1: Traverse the linked list and store the elements in an array
    arr = []
    current = head
    while current is not None:
        arr.append(current.val)
        current = current.next
    
    # Step 2: Sort the array
    arr.sort()
    
    # Step 3: Return the sorted array
    return arr
```

The time complexity of this solution is O(n log n), where n is the number of nodes in the linked list. This is due to the sorting step, as we traverse the linked list in O(n) time to populate the array and then sort it in O(n log n) time. The space complexity is O(n) because we are storing all the elements from the linked list in an array. Given that the constraints specify a linked list can contain integers in any order, this solution efficiently handles the sorting requirement.

1. **Empty Linked List**: If the linked list is empty (head is None), the function should return an empty array `[]`. 
2. **Single Element**: If there is only one element in the linked list, the sorted array should simply return that element as a single-element list, e.g., for linked list [5], the output should be `[5]`. 
3. **All Elements Identical**: If all elements in the linked list are the same, the output should be an array of that element repeated, e.g., for linked list [2 -> 2 -> 2], the output should be `[2, 2, 2]`.

Transform linked list to sorted array

Goldman Sachs

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Goldman Sachs Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string