Partition List

Given a singly linked list and a pivot value, rearrange the list such that all nodes with values less than the pivot come before all nodes with values greater than or equal to the pivot. The relative order of nodes within each partition should be preserved. This is a common operation in sorting algorithms like quicksort and is useful for organizing data based on a threshold.

Problem Description

You are tasked with implementing a function that partitions a singly linked list. The function will take the head of the linked list and an integer pivot as input. The goal is to rearrange the list so that all nodes whose values are strictly less than the pivot appear before all nodes whose values are greater than or equal to the pivot. Crucially, the relative order of nodes within the "less than" partition and within the "greater than or equal to" partition must remain unchanged from their original order in the input list.

Key Requirements:

• The function must modify the existing linked list in-place, if possible, or create a new partitioned list.
• All nodes with values less than pivot must precede all nodes with values greater than or equal to pivot.
• The original relative order of nodes within the "less than" group must be preserved.
• The original relative order of nodes within the "greater than or equal to" group must be preserved.

Expected Behavior:

The function should return the head of the newly partitioned linked list.

Edge Cases to Consider:

• An empty linked list.
• A linked list with only one node.
• All nodes have values less than the pivot.
• All nodes have values greater than or equal to the pivot.
• The pivot value is not present in the list.

Examples

Example 1:

Input:
head = 1 -> 4 -> 3 -> 2 -> 5 -> 2
pivot = 3

Output:
1 -> 2 -> 2 -> 4 -> 3 -> 5

Explanation: The nodes with values less than 3 are 1, 2, and 2. Their original relative order is 1, 2, 2. The nodes with values greater than or equal to 3 are 4, 3, and 5. Their original relative order is 4, 3, 5. The output list preserves these relative orders within their respective partitions.

Example 2:

Input:
head = 2 -> 1
pivot = 2

Output:
1 -> 2

Explanation: The node with value less than 2 is 1. The node with value greater than or equal to 2 is 2. The output is 1 -> 2.

Example 3:

Input:
head = 5 -> 4 -> 3 -> 2 -> 1
pivot = 0

Output:
5 -> 4 -> 3 -> 2 -> 1

Explanation: No nodes have values less than 0. All nodes are greater than or equal to 0. The list remains unchanged.

Constraints

• The number of nodes in the linked list will be between 0 and 1000.
• The value of each node will be an integer between -1000 and 1000.
• The pivot value will be an integer between -1000 and 1000.
• The linked list nodes will have a value field and a next field pointing to the subsequent node or null (or equivalent sentinel) for the last node.
• The algorithm should aim for a time complexity of O(N), where N is the number of nodes in the list.
• The algorithm should aim for a space complexity of O(1) if modifying in-place, or O(N) if creating a new list.

Notes

Consider using two separate linked lists (or dummy heads for them) to build the "less than" and "greater than or equal to" partitions. After iterating through the original list and appending nodes to the appropriate partition, you can then concatenate these two partitions to form the final result. Remember to handle the next pointers correctly, especially for the tail of each partition and the connection between them.