mediumLinked ListPattern: Combined
Sortable Linked List Solution
Problem Statement
Given a linked list of elements with unique identifiers, implement a data structure to efficiently insert new elements into the list while maintaining a sorted order and remove existing elements.
Examples
Example 1:
Input:{1, 3, 5, 7, 9}
Output:{1, 2, 3, 5, 7, 9}
Explanation: Inserting a new element (2) at the correct position: {1, 2, 3, 5, 7, 9}
Example 2:
Input:{10, 20, 30, 40, 50}
Output:{10, 20, 30, 40, 50}
Explanation: Deleting an existing element (30) from the list: {10, 20, 40, 50}
Example 3:
Input:{5, 5, 5, 5}
Output:{5, 5, 5, 5}
Explanation: Inserting a new element with different value: {5, 5, 5, 5}
Constraints
- The linked list should be sorted in ascending order.
- Elements with duplicate values should be kept.
- The linked list should be implemented iteratively.
Time: O(n) Space: O(1)
Use a single pass through the linked list to insert or delete elements, maintaining the sorted order.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def sortable_linked_list(arr):
sorted_arr = sorted(set(arr))
dummy = ListNode()
tail = dummy
for num in sorted_arr:
tail.next = ListNode(num)
tail = tail.next
return dummy.next