NUHMAN.com

Introduction

LeetCode 86: Partition List is a Linked List problem where you are tasked with partitioning a singly linked list around a given value x. The goal is to rearrange the list such that all nodes less than x come before nodes greater than or equal to x, while maintaining the original relative order of the nodes.

This problem is an excellent exercise in linked list manipulation and is frequently encountered in coding interviews, especially for two-pointer solutions.

Problem Statement

Given a head of a singly linked list and a value x, partition the list so that all nodes with values less than x come before nodes with values greater than or equal to x. You must do it in one-pass and without using extra memory for another list (i.e., in-place modification).

Example:

go

Input: head = 1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3
Output: 1 -> 2 -> 2 -> 4 -> 3 -> 5

Approach: Two Pointers

Strategy:

We can use two linked lists to achieve this:

1. One list for nodes less than x.
2. Another list for nodes greater than or equal to x.

At the end, we’ll combine these two lists, maintaining their relative order.

Steps:

1. Traverse the original list, and for each node:

• If its value is less than x, append it to the first list.
• If its value is greater than or equal to x, append it to the second list.

1. After traversing, connect the last node of the first list to the head of the second list.
2. Return the head of the first list as the new partitioned list.

Go Implementation

go

type ListNode struct {
    Val  int
    Next *ListNode
}

func partition(head *ListNode, x int) *ListNode {
    // Create two dummy nodes for the less and greater lists
    lessHead := &ListNode{}
    greaterHead := &ListNode{}
    
    // Initialize two pointers for both lists
    less := lessHead
    greater := greaterHead
    
    // Traverse through the original list
    for head != nil {
        if head.Val < x {
            // Add to the "less" list
            less.Next = head
            less = less.Next
        } else {
            // Add to the "greater" list
            greater.Next = head
            greater = greater.Next
        }
        head = head.Next
    }
    
    // Make sure the last node of the "greater" list points to nil
    greater.Next = nil
    
    // Connect the "less" list with the "greater" list
    less.Next = greaterHead.Next
    
    // Return the head of the partitioned list
    return lessHead.Next
}

Explanation

• lessHead and greaterHead: We use two dummy nodes to represent the start of the less and greater partitions.
• Pointers (less and greater): These pointers track the last node added to each partition.
• As we traverse the list, we compare each node’s value to x:
• If less than x, it’s added to the less list.
• If greater than or equal to x, it’s added to the greater list.
• Finally, we connect the less list to the greater list, and return lessHead.Next to skip the dummy node and return the correct result.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Where n is the number of nodes in the list. We only use a few extra pointers for the two partitions, making it an in-place solution.

Edge Cases

• Empty list: If the input head is nil, the result should also be nil.
• All nodes are less than x: The list remains unchanged.
• All nodes are greater than or equal to x: The list remains unchanged.
• x is greater than all nodes: All nodes will be in the greater list.
• x is less than all nodes: All nodes will be in the less list.

Conclusion

LeetCode 86 is an excellent problem to practice linked list manipulation using two-pointer techniques. The key here is to partition the list into two separate lists for values less than x and greater than or equal to x while maintaining the order, then combining the lists efficiently.

This solution efficiently handles the task in one pass and uses constant space (besides the space for the input list), making it both time and space efficient.