2046. Sort Linked List Already Sorted Using Absolute Values

MediumLinked ListTwo PointersSorting
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

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:

  1. Initialize two pointers prev and curr. prev starts at the head of the list, and curr starts at the second element (head.next), since there is no need to move the head itself.
  2. Iterate through the linked list with a while loop, which continues until curr is None, meaning we've reached the end of the list.
  3. 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 setting prev.next to curr.next. This removes the current node from its position in the list. b. Move the curr node to the front by setting curr.next to head. This places the current node at the beginning of the list. c. Update head to be curr since curr is now the new head of the list. d. Move the curr pointer to the next node in the list by setting it to t (the node following the moved node).
    • If curr.val is not negative, we simply move forward in the list by setting prev to curr and curr to curr.next, as no changes are needed for non-negative or zero values.
  4. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example 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:

  1. We initialize prev as the head (node with value 2) and curr as the second node (node with value -3).
  2. We start the while loop and iterate over the list. In our example, the first curr is negative.
  3. Since the value of curr (-3) is negative, we insert it before the head: a. Detach curr: we remove -3 from the list. The list becomes: 2 -> -4 -> 5 -> 6 b. Move curr to the front: we insert -3 before the current head. The list becomes: -3 -> 2 -> -4 -> 5 -> 6 c. Update head to curr: -3 is the new head of the list. d. Move curr to next node: curr now points to -4.
  4. Repeat the process for the next curr, which again has a negative value (-4): a. Detach curr: we remove -4 from the list. The list becomes: -3 -> 2 -> 5 -> 6 b. Move curr to the front: we insert -4 before the head. The list becomes: -4 -> -3 -> 2 -> 5 -> 6 c. Update head to curr: -4 is the new head of the list. d. Move curr to next node: curr now points to 5.
  5. Now curr points to a positive value (5), so we just move the prev to curr and curr to its next node, which is 6.
  6. As curr points to another positive value (6), we again just advance prev and curr accordingly.
  7. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which technique can we use to find the middle of a linked list?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Linked List Cycle

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

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 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 Two pointers is a common interview technique

Sorting Summary

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ