python partition list

Guri Bee

3 min read

·

21-10-2024

1

0

Share

Partitioning a Linked List in Python: A Comprehensive Guide

Partitioning a linked list is a classic problem in data structures and algorithms. It involves rearranging the nodes in a linked list so that all nodes with values less than a given x come before all nodes with values greater than or equal to x. This article will guide you through the process of partitioning a linked list in Python, explaining the logic and providing practical examples.

Understanding the Problem

Imagine you have a linked list containing the following elements: 1 -> 4 -> 3 -> 2 -> 5. The task is to partition this list around the value 3. The resulting partitioned list should look like this: 1 -> 2 -> 3 -> 4 -> 5. Notice how all nodes with values less than 3 (1, 2) appear before the nodes with values greater than or equal to 3 (3, 4, 5).

Python Implementation

Let's dive into a Python implementation for partitioning a linked list:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def partition(head, x):
    """
    Partitions a linked list around a value x.

    Args:
        head: The head of the linked list.
        x: The pivot value.

    Returns:
        The new head of the partitioned linked list.
    """

    before_head = Node(0)
    before = before_head
    after_head = Node(0)
    after = after_head
    
    current = head
    while current:
        if current.data < x:
            before.next = current
            before = before.next
        else:
            after.next = current
            after = after.next
        current = current.next

    after.next = None
    before.next = after_head.next

    return before_head.next

Explanation

1. Initialization: We create two dummy nodes, before_head and after_head, to keep track of the start of the partitioned lists for values less than x and greater than or equal to x, respectively. We also initialize before and after pointers to point to these dummy nodes.

2. Iteration: We traverse the linked list using current and compare each node's data with the pivot value x.

3. Partitioning:

   • If the current node's data is less than x, we append it to the before list by setting before.next to the current node and updating before to point to the new node.
   • If the current node's data is greater than or equal to x, we append it to the after list in the same way.

4. Joining the Partitions: After iterating through all nodes, we set the next pointer of the after list to None to signify the end of the list. Then, we connect the before list to the after list by setting before.next to after_head.next.

5. Return: We return the head of the partitioned list, which is before_head.next.

Example Usage

# Create a linked list
head = Node(1)
head.next = Node(4)
head.next.next = Node(3)
head.next.next.next = Node(2)
head.next.next.next.next = Node(5)

# Partition the list around x = 3
new_head = partition(head, 3)

# Print the partitioned list
while new_head:
    print(new_head.data, end=" ")
    new_head = new_head.next

Output:

1 2 3 4 5 

Key Points

• Time Complexity: The partitioning process takes O(n) time, where n is the number of nodes in the linked list, as we iterate through each node once.
• Space Complexity: We use O(1) extra space, as we only create a few additional pointers.
• In-Place Modification: The partitioning happens directly on the existing linked list, modifying the next pointers to rearrange the nodes.

Conclusion

Partitioning a linked list is a fundamental technique in linked list manipulation. Understanding how to efficiently partition a list can be valuable in various applications involving data sorting and organization. This article has provided a comprehensive guide to implementing the partitioning process in Python, empowering you to solve this common data structure problem. Remember, practice is key to mastery; experiment with different input lists and pivot values to solidify your understanding of linked list partitioning.