easyLinked ListPattern: Combined
Sort Linked List by Timestamp Solution
Problem Statement
Given the head of a singly linked list where each node contains an integer `data` and a non-negative integer `timestamp`. Your task is to sort the linked list in ascending order based on the `timestamp` values. If two nodes have the same `timestamp`, their relative order should be preserved (stable sort). Return the head of the sorted linked list.
Examples
Example 1:
Input:Nodes: [(data: 10, timestamp: 1678886400), (data: 5, timestamp: 1678882800), (data: 20, timestamp: 1678884600)]
Output:Nodes: [(data: 5, timestamp: 1678882800), (data: 20, timestamp: 1678884600), (data: 10, timestamp: 1678886400)]
Explanation: The nodes are sorted based on their timestamps: 1678882800, 1678884600, 1678886400. The corresponding data values are 5, 20, and 10.
Example 2:
Input:Nodes: [(data: 3, timestamp: 100), (data: 7, timestamp: 200), (data: 1, timestamp: 100)]
Output:Nodes: [(data: 3, timestamp: 100), (data: 1, timestamp: 100), (data: 7, timestamp: 200)]
Explanation: Nodes with timestamp 100 are 3 and 1. Since the sort must be stable, their original relative order is maintained (3 before 1). The node with timestamp 200 comes last.
Example 3:
Input:Nodes: [(data: 50, timestamp: 500)]
Output:Nodes: [(data: 50, timestamp: 500)]
Explanation: A list with a single node is already sorted.
Constraints
- The number of nodes in the list is between 0 and 10^5.
- Each node's `data` value is an integer.
- Each node's `timestamp` value is a non-negative integer.
- Timestamps can range from 0 to 2^32 - 1.
Time: O(N log N) Space: O(log N) for recursive stack, or O(1) if iterative merge sort is used.
A more efficient approach for linked lists is to use a merge sort. Recursively divide the list into halves until you have sublists of size 0 or 1. Then, merge these sorted sublists back together in a stable manner based on timestamps. This can be done in-place (with O(log n) stack space for recursion) or with minimal auxiliary space.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
class ListNode:
def __init__(self, data=0, timestamp=0, next=None):
self.data = data
self.timestamp = timestamp
self.next = next
def sort_list_by_timestamp(head):
if not head or not head.next:
return head
# Split the list into two halves
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# Recursively sort the two halves
left = sort_list_by_timestamp(head)
right = sort_list_by_timestamp(mid)
# Merge the sorted halves
return merge(left, right)
def merge(l1, l2):
dummy = ListNode(0, 0)
current = dummy
while l1 and l2:
if l1.timestamp <= l2.timestamp:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
if l1:
current.next = l1
if l2:
current.next = l2
return dummy.next