**π‘ Problem Formulation:** Imagine you have a linked list with numeric values, and you need to rearrange the nodes so that all nodes less than a certain value `k`

come before nodes equal to or greater than `k`

. For example, given a linked list `1 -> 4 -> 3 -> 2 -> 5 -> 2`

and `k = 3`

, the desired output would be `1 -> 2 -> 2 -> 4 -> 3 -> 5`

, with all nodes less than 3 moved to the front.

## Method 1: Partitioning and Merging

This method involves separating the linked list into two sub-lists: one for nodes less than `k`

, and another for nodes equal to or greater than `k`

. Then, the two lists are merged back together. It ensures that the relative order of nodes in each partition is preserved.

Here’s an example:

class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next def arrange_linked_list(head, k): smaller_head = smaller_tail = ListNode(0) greater_head = greater_tail = ListNode(0) while head: if head.value 4 -> 3 -> 2 -> 5 -> 2 and k=3 nodes = [ListNode(2), ListNode(5), ListNode(2), ListNode(3), ListNode(4), ListNode(1)] for i in range(len(nodes)-1, 0, -1): nodes[i].next = nodes[i-1] head = nodes[-1] new_head = arrange_linked_list(head, 3)

The output would be a reordered linked list: `1 -> 2 -> 2 -> 4 -> 3 -> 5`

.

In this snippet, we define a `ListNode`

class to hold value and next pointers for a linked list. The `arrange_linked_list`

function then creates two dummy nodes to ease the partitioning process. It iterates through the list and appends nodes to the respective ‘smaller’ or ‘greater’ lists. After the loop, the ‘greater’ list is appended to the ‘smaller’ list, and the merged list is returned.

## Method 2: In-Place Rearrangement

This method involves rearranging the nodes in-place without creating any new nodes. It requires careful manipulation of the next pointers to move smaller valued nodes to the front as they are encountered.

Here’s an example:

def rearrange_in_place(head, k): if not head: return None current = head tail = head while tail.next: tail = tail.next # Initial reference to tail ensures that nodes moved to front will not be re-processed. original_tail = tail while current != original_tail: if current.value >= k and current != head: tail.next = current tail = current current = current.next tail.next = None elif current.value >= k and current == head: head = head.next tail.next = current tail = current current.next = None current = head else: current = current.next return head # Usage remains the same as the example from Method 1

The output would be a reordered linked list: `1 -> 2 -> 2 -> 4 -> 3 -> 5`

.

This code rearranges the list in-place by iterating through the list until it reaches the original tail node. If a node’s value is greater than or equal to `k`

(and it’s not the head), it’s moved to the end. If the current node is the head, the head is updated, and the node is moved to the end. This avoids using additional space for extra lists.

## Method 3: Using Two-Pointer Technique

Two-pointer technique is used to traverse the list. One pointer is used to keep track of the most recent node less than k, while the second pointer scans ahead to find the next node less than k to swap into position.

Here’s an example:

def two_pointer_rearrange(head, k): if not head: return None last_node_under_k = head if head.value < k else None current = head.next if last_node_under_k else head while current: if current.value < k: if not last_node_under_k: head = current else: last_node_under_k.next, current.next, current = current, last_node_under_k.next, current.next continue last_node_under_k = current current = current.next return head # Usage is similar to the above examples.

The output would be a reordered linked list: `1 -> 2 -> 2 -> 4 -> 3 -> 5`

.

The code moves nodes with values less than `k`

towards the front of the list using two pointers. It begins by setting `last_node_under_k`

to either the head or None, depending on whether the head node’s value meets the condition. As it scans through, when it finds the next node under k, it performs pointer swaps without actually creating new nodes.

## Method 4: Recursion

The recursive approach uses the call stack to hold nodes, popping them off in the new order once the base case at the end of the list is met. It divides the problem into smaller sub-problems, dealing with one node per recursion level.

Here’s an example:

def rearrange_recursively(head, k): if not head or not head.next: return head new_head = rearrange_recursively(head.next, k) if head.value < k: head.next = new_head return head else: current = new_head while current.next and current.next.value < k: current = current.next head.next, current.next = current.next, head return new_head # Usage is similar to the above examples.

The output would be a reordered linked list: `1 -> 2 -> 2 -> 4 -> 3 -> 5`

.

This snippet uses recursion to process the list. It returns early for lists with zero or one node, as there’s nothing to rearrange. It captures the head of the rearranged sub-list, then decides where to place the current node relative to the sub-list, ensuring that nodes with values below `k`

are moved to the front.

## Bonus One-Liner Method 5: List Comprehension and Construction

A Pythonic and concise one-liner approach involves using list comprehension to build the list nodes directly from a given list of values in the desired order.

Here’s an example:

# Assuming existing ListNode class and a list of nodes 'nodes' values = [node.value for node in nodes] new_head = ListNode(0) pointer = new_head for value in [v for v in values if v = k]: pointer.next = ListNode(value) pointer = pointer.next # The variable `new_head.next` is the head of the new list.

The new ordered list: `1 -> 2 -> 2 -> 4 -> 3 -> 5`

.

The one-liner command combines two list comprehensions: one filters values less than `k`

and the other for values greater than or equal to `k`

, concatenating them. New nodes are then created based on this ordered list.

## Summary/Discussion

**Method 1: Partitioning and Merging.**This method preserves the original node’s order. However, it uses O(n) additional space and multiple iterations.**Method 2: In-Place Rearrangement.**No extra space is used, preserving space complexity at O(1). It is more complex to implement and requires careful handling of pointers.**Method 3: Two-Pointer Technique.**This approach is slightly more complex but keeps space usage minimal. May not preserve the order of larger elements.**Method 4: Recursion.**Elegant and simpler to understand but has the overhead of recursion stack which can be a problem for large lists.**Method 5: List Comprehension and Construction.**A pythonic and concise solution. This approach does not preserve the original list nodes, requiring the list to be duplicated.