2046. Sort Linked List Already Sorted Using Absolute Values
Problem Description
The given problem asks us to take the head
of a singly-linked list, where the list is sorted in non-decreasing order based on the absolute values of its nodes. The goal is to re-sort this list, but this time according to the actual values of its nodes, still maintaining a non-decreasing order. This challenge essentially involves sorting negative numbers (where applicable) before the non-negative ones while adhering to the non-decreasing sequence.
Intuition
The intuition behind the solution is to leverage the fact that the list is already sorted by absolute values. This characteristic implies that all negative values, if any, will be at the beginning of the list - but they will be in decreasing order because their absolute values are sorted in non-decreasing order. Conversely, the non-negative values will follow in non-decreasing order.
Therefore, the solution approach involves iterating through the list and moving any encountered negative values to the front. Since we know that the list is effectively partitioned into a non-increasing sequence of negative values followed by a non-decreasing sequence of non-negative values, moving each negative value we encounter to the front of the list will naturally sort it.
By iterating just once through the linked list, whenever a negative value is found, it's plucked out of its position and inserted before the current head
. This insert-at-head operation ensures that the ultimately larger (less negative) values encountered later are placed closer to the head, thereby achieving a non-decreasing order of actual values.
The key points of the approach are:
- No need for a complex sorting algorithm since the list is already sorted by absolute values.
- Negative values must precede non-negative ones for actual value sorting.
- Iterating just once throughout the list is sufficient.
- A simple insert-at-head operation for negative values during iteration results in the desired sorted order.
The solution preserves the initial list's order in terms of absolute values while reordering only where necessary to get the actual values sorted, hence achieving the re-sorting in an efficient manner.
Learn more about Linked List, Two Pointers and Sorting patterns.
Solution Approach
The provided solution uses a simple while loop and direct manipulation of the linked list nodes to achieve the task without additional data structures.
The algorithm follows these steps:
- Initialize two pointers
prev
andcurr
.prev
starts at thehead
of the list, andcurr
starts at the second element (head.next
), since there is no need to move the head itself. - Iterate through the linked list with a
while
loop, which continues untilcurr
isNone
, meaning we've reached the end of the list. - For each node, we check if
curr.val
is negative.- If it is negative, we conduct the following re-linking process:
a. Detach the
curr
node by settingprev.next
tocurr.next
. This removes the current node from its position in the list. b. Move thecurr
node to the front by settingcurr.next
tohead
. This places the current node at the beginning of the list. c. Updatehead
to becurr
sincecurr
is now the new head of the list. d. Move thecurr
pointer to the next node in the list by setting it tot
(the node following the moved node). - If
curr.val
is not negative, we simply move forward in the list by settingprev
tocurr
andcurr
tocurr.next
, as no changes are needed for non-negative or zero values.
- If it is negative, we conduct the following re-linking process:
a. Detach the
- Repeat this process until the
curr
pointer reaches the end of the list.
The algorithm uses the two-pointer technique to traverse and manipulate the linked list in place without requiring extra space for sorting. The key insight here is that the insertion of negative nodes at the head can be done in constant time, which makes the solution very efficient. There are no complicated data structures or algorithms needed; the solution makes direct alterations to the list's nodes, which takes advantage of the properties of linked lists for efficient insertion operations.
As for complexity:
- The time complexity is O(n), where
n
is the number of nodes in the list, since every node is visited once. - The space complexity is O(1), as no additional space proportional to the input size is used.
This approach is efficient and takes advantage of the already partially sorted nature of the list based on absolute values to achieve the fully sorted list by actual values with minimal operations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the following singly-linked list sorted by absolute values:
2 -> -3 -> -4 -> 5 -> 6
According to the problem statement, our goal is to reorder this list based on the actual values, preserving non-decreasing order.
Here's a step-by-step walkthrough using the solution approach provided:
- We initialize
prev
as thehead
(node with value 2) andcurr
as the second node (node with value -3). - We start the
while
loop and iterate over the list. In our example, the firstcurr
is negative. - Since the value of
curr
(-3) is negative, we insert it before the head: a. Detachcurr
: we remove -3 from the list. The list becomes:2 -> -4 -> 5 -> 6
b. Movecurr
to the front: we insert -3 before the current head. The list becomes:-3 -> 2 -> -4 -> 5 -> 6
c. Updatehead
tocurr
: -3 is the new head of the list. d. Movecurr
to next node:curr
now points to -4. - Repeat the process for the next
curr
, which again has a negative value (-4): a. Detachcurr
: we remove -4 from the list. The list becomes:-3 -> 2 -> 5 -> 6
b. Movecurr
to the front: we insert -4 before the head. The list becomes:-4 -> -3 -> 2 -> 5 -> 6
c. Updatehead
tocurr
: -4 is the new head of the list. d. Movecurr
to next node:curr
now points to 5. - Now
curr
points to a positive value (5), so we just move theprev
tocurr
andcurr
to its next node, which is 6. - As
curr
points to another positive value (6), we again just advanceprev
andcurr
accordingly. - We've reached the end of the list. The list is now correctly sorted by actual values in non-decreasing order:
-4 -> -3 -> 2 -> 5 -> 6
While iterating through the list, we only moved the negative values, which were already sorted in non-increasing order, to the front. We didn't need to touch the positive values because they were already in non-decreasing order. This process respects the previously sorted absolute values while ordering the elements by their actual values.
Solution Implementation
1# Definition for a singly-linked list node.
2class ListNode:
3 def __init__(self, val=0, next=None):
4 self.val = val # Value of the node
5 self.next = next # Reference to the next node in the list
6
7class Solution:
8 def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:
9 # Initialize pointers.
10 # `previous` will track the node before `current`.
11 previous = None
12 current = head
13
14 # Traverse the linked list starting from the head until there are no more nodes.
15 while current:
16 # Check if the current node's value is negative.
17 if current.val < 0:
18 # If this is the first node (head of the list), no need to move it.
19 if previous is None:
20 current = current.next
21 continue
22
23 # If current node is negative, shift it to the beginning of the list.
24 previous.next = current.next # Link the previous node to the next node, effectively removing `current` from its current position
25 current.next = head # Make `current` node point to the current head
26 head = current # Update `head` to be the `current` node
27
28 # Move on to the next node
29 current = previous.next
30 else:
31 # If current node is not negative, just move `previous` and `current` pointers one step forward.
32 previous = current
33 current = current.next
34
35 return head # Return the modified list with all negative values moved to the beginning
36
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5 int val;
6 ListNode next;
7
8 ListNode() {}
9
10 ListNode(int val) { this.val = val; }
11
12 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
13}
14
15class Solution {
16 /**
17 * This method sorts a linked list such that all nodes with negative values
18 * are moved to the front.
19 *
20 * @param head The head of the singly-linked list.
21 * @return The head of the sorted singly-linked list.
22 */
23 public ListNode sortLinkedList(ListNode head) {
24 // Previous and current pointers for traversal
25 ListNode previous = head;
26 ListNode current = head.next;
27
28 // Iterate through the list
29 while (current != null) {
30 // When a negative value is encountered
31 if (current.val < 0) {
32 // Detach the current node with the negative value
33 ListNode temp = current.next;
34 previous.next = temp;
35
36 // Move the current node to the front of the list
37 current.next = head;
38 head = current;
39
40 // Continue traversal from the next node
41 current = temp;
42 } else {
43 // If the current value is not negative, move both pointers forward
44 previous = current;
45 current = current.next;
46 }
47 }
48
49 // Return the updated list with all negative values at the front
50 return head;
51 }
52}
53
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode() : val(0), next(nullptr) {}
7 * ListNode(int x) : val(x), next(nullptr) {}
8 * ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13 ListNode* sortLinkedList(ListNode* head) {
14 // Initialize pointers for traversal
15 ListNode* previous = head; // Pointer to track the node just before the current one
16 ListNode* current = head->next; // Pointer to track the current node during traversal
17
18 // Iterate through the list
19 while (current != nullptr) {
20 // When the current node has a negative value, reposition it to the start of the list
21 if (current->val < 0) {
22 ListNode* temp = current->next; // Hold the next node to continue traversal later
23 previous->next = temp; // Remove the current node from its original position
24 current->next = head; // Insert the current node at the beginning of the list
25 head = current; // Update the head to the new first node
26 current = temp; // Continue traversal from the next node
27 } else {
28 // If the current node is non-negative, move both pointers forward
29 previous = current;
30 current = current->next;
31 }
32 }
33
34 return head; // Return the sorted list
35 }
36};
37
1/**
2 * Definition for singly-linked list.
3 */
4interface ListNode {
5 val: number;
6 next: ListNode | null;
7}
8
9/**
10 * Sorts a singly linked list such that all negative values are moved to the front.
11 * @param {ListNode | null} head - The head of the linked list to be sorted.
12 * @returns {ListNode | null} The head of the sorted linked list.
13 */
14function sortLinkedList(head: ListNode | null): ListNode | null {
15 // There is nothing to sort if the list is empty or has only one node.
16 if (!head || !head.next) {
17 return head;
18 }
19
20 // Initialize pointers for traversal.
21 let previous: ListNode | null = head; // Pointer to track the node just before the current one.
22 let current: ListNode | null = head.next; // Pointer to track the current node during traversal.
23
24 // Iterate through the list.
25 while (current !== null) {
26 // When the current node has a negative value, reposition it to the start of the list.
27 if (current.val < 0) {
28 let temp: ListNode | null = current.next; // Hold the next node to continue traversal later.
29 previous.next = temp; // Remove the current node from its original position.
30 current.next = head; // Insert the current node at the beginning of the list.
31 head = current; // Update the head to the new first node.
32 current = temp; // Continue traversal from the next node.
33 } else {
34 // If the current node is non-negative, move both pointers forward.
35 previous = current;
36 current = current.next;
37 }
38 }
39
40 // Return the head of the sorted list.
41 return head;
42}
43
Time and Space Complexity
Time Complexity
The given code is intended to sort a singly-linked list by moving all negative value nodes to the beginning of the list in one pass. It iterates through the list only once, with a fixed set of actions for each node. The main operations within the loop involve pointer adjustments which take constant time. Hence, no matter the input size of the singly-linked list, the algorithm guarantees that each element is checked exactly once.
The time complexity of the code is O(n)
, where n
is the number of nodes in the linked list.
Space Complexity
The space complexity of the code is related to the extra space used by the algorithm, excluding the space for the input.
The provided code uses a constant amount of space: variables prev
, curr
, and t
. No additional data structures are used that grow with the input size. All changes are made in-place by adjusting the existing nodes' next
pointers.
Thus, the space complexity of the code is O(1)
since it uses constant extra space.
Learn more about how to find time and space complexity quickly using problem constraints.
You are given an array of intervals where intervals[i] = [start_i, end_i]
represent the start and end of the ith
interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced