Transform linked list to sorted array

Question

Given a linked list of integers, write a function to transform it into a sorted array. The output should be an array containing the elements of the linked list in ascending order. Ensure that your solution efficiently handles the linked list traversal and sorting.

Codemia · Accepted Answer

To transform a linked list into a sorted array, we need to first traverse the linked list to extract its elements and then sort them. The specific patterns that apply here are:

1. **Linked List Traversal**: We will need to iterate through the linked list to gather all the elements. This is a straightforward linear traversal, which is O(n) in complexity, where n is the number of nodes in the linked list.
2. **Sorting**: After collecting the elements into an array, we will sort this array. The sorting will generally take O(n log n) time.

Since we are only required to return a sorted array and not modify the linked list, a direct approach of collecting values followed by sorting is efficient and clear.

Here’s the step-by-step algorithm to solve the problem:

1. **Initialize an empty list**: Create an empty list to hold the values extracted from the linked list.
2. **Traverse the linked list**: Use a loop to go through each node of the linked list. For each node, append its value to the list created in step 1.
3. **Sort the list**: Once all values have been collected, utilize Python's built-in sorting method to sort the list.
4. **Return the sorted list**: Finally, return the sorted list as the result.

**Example**: 
- Input: Linked List -> 3 -> 1 -> 4 -> 2
- Step 1: Extracted List: [3, 1, 4, 2]
- Step 2: Sorted List: [1, 2, 3, 4]
- Output: [1, 2, 3, 4]

Here is the Python solution for the problem:
```python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def linked_list_to_sorted_array(head):
    values = []
    current = head
    # Step 2: Traverse the linked list
    while current:
        values.append(current.value)
        current = current.next
    # Step 3: Sort the list
    values.sort()
    # Step 4: Return the sorted list
    return values
```
This code defines a ListNode class for the linked list nodes and implements the `linked_list_to_sorted_array` function that follows our outlined approach.

The time and space complexity for this solution is as follows:

1. **Time Complexity**: The traversal of the linked list takes O(n) time, where n is the number of nodes. The sorting operation takes O(n log n) time. Therefore, the overall time complexity is O(n log n) due to the sorting step.
2. **Space Complexity**: We use a list to store the values extracted from the linked list, which requires O(n) space for storing these values. There are no other significant space-consuming operations, so the space complexity remains O(n).

We need to handle some edge cases for this function:

1. **Empty Linked List**: If the linked list is empty (i.e., `head` is None), the function should return an empty array `[]`.
2. **Single Element Linked List**: If the linked list contains only one element, the function should return an array with that single element.
3. **Duplicates in Linked List**: The function should appropriately handle cases where there are duplicate values in the linked list and return them in the sorted array.

**Example Edge Cases**:
- Input: `None` (empty list) → Output: `[]`
- Input: `1` (one element) → Output: `[1]`
- Input: `1 -> 2 -> 2 -> 3` → Output: `[1, 2, 2, 3]`

Transform linked list to sorted array

HRT

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

HRT 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