How do you solve Partition List on LeetCode?

Partition List (LeetCode #86) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using two pointers helps maintain the order of nodes efficiently.

What is the brute force solution for Partition List?

The brute force approach for Partition List is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves creating two separate lists: one for nodes less than x and another for nodes greater than or equal to x. After traversing the original list, we can concatenate these two lists to form the final partitioned list. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Partition List?

Partition List uses the following concepts: Linked List, Two Pointers. The recommended patterns to study are: Two Pointers, Linked List.

What are the interview tips for Partition List?

Explain your thought process clearly before coding. Consider edge cases like empty lists or lists with all elements less than or greater than x. Practice writing clean and concise code.

What are common mistakes when solving Partition List?

Not properly terminating the greater list, which can lead to cycles. Forgetting to connect the two lists after partitioning.

#86

Partition List

Medium

Linked ListTwo PointersTwo PointersLinked List

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses two pointers to traverse the linked list in a single pass, maintaining two separate lists for nodes less than x and nodes greater than or equal to x. This approach is efficient and preserves the order of nodes.

⚙️

Algorithm

3 steps

1Step 1: Initialize two dummy nodes for the less and greater lists.
2Step 2: Traverse the original list once, adding nodes to the appropriate list based on their value relative to x.
3Step 3: Connect the end of the less list to the head of the greater list and return the head of the less list.

solution.py22 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def partition(head, x):
8    less_head = ListNode(0)
9    greater_head = ListNode(0)
10    less = less_head
11    greater = greater_head
12    while head:
13        if head.val < x:
14            less.next = head
15            less = less.next
16        else:
17            greater.next = head
18            greater = greater.next
19        head = head.next
20    greater.next = None  # End the greater list
21    less.next = greater_head.next  # Connect the two lists
22    return less_head.next

ℹ

Complexity note: The time complexity is O(n) because we traverse the list only once. The space complexity is O(1) since we are using a constant amount of extra space for the pointers.

1Using two pointers helps maintain the order of nodes efficiently.
2Creating dummy nodes simplifies the handling of edge cases.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.