5 Best Ways to Arrange Linked List Nodes Based on Value k in Python

Rate this post

πŸ’‘ 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.