MediumLinked ListsAI interview only
Sort Linked List Already Sorted Using Absolute Values
Asked atamazonmicrosoftmetagoogle
01 · Problem
You are given the head of a singly linked list whose nodes are sorted in non-decreasing order of absolute value. Rearrange the nodes so that the list is sorted in non-decreasing order of actual value, and return the new head.
Aim for O(n) time and O(1) extra space by relinking nodes rather than running a general-purpose sort.
02 · Examples
Example 01
Input
head = [1,-2,-3,4]
Output
[-3,-2,1,4]
By actual value, -3 < -2 < 1 < 4.
Example 02
Input
head = [0,-1,1,-4,6]
Output
[-4,-1,0,1,6]
The negative nodes -1 and -4 move to the front in reverse order of their appearance; the non-negative nodes keep their order.
Example 03
Input
head = [-7]
Output
[-7]
A single node is already sorted.
03 · Constraints
- 01The number of nodes in the list is in the range [1, 105].
- 02-5000 <= Node.val <= 5000
- 03The list is sorted in non-decreasing order of absolute value.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.