#86

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Partition List

Partition a linked list such that all nodes less than x come before nodes greater than or equal to x while preserving relative order.

linked list two pointers

Problem Statement

You are given the head of a linked list and an integer x. You must partition the list such that all nodes with values less than x come before nodes with values greater than or equal to x. The original relative order of the nodes should be preserved within each partition.

For example, given the list [1,4,3,2,5,2] and x = 3, the expected output would be [1,2,2,4,3,5].

Examples

Example 1

Input: head = [1,4,3,2,5,2], x = 3

Output: [1,2,2,4,3,5]

Example details omitted.

Example 2

Input: head = [2,1], x = 2

Output: [1,2]

Example details omitted.

Constraints

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

Solution Approach

Two-pointer technique

Utilize two pointers to separate nodes into two lists: one for values less than x and another for values greater than or equal to x. The first pointer traverses the list to identify nodes that should go in the 'less than x' partition, while the second pointer handles the 'greater than or equal to x' partition.

Re-linking nodes

After identifying the appropriate nodes for each partition, the lists must be re-linked together by connecting the 'less than x' partition with the 'greater than or equal to x' partition. This can be done by adjusting the next pointers of the last node in the 'less than x' partition.

Edge case handling

Consider edge cases such as an empty list or when all nodes are less than or greater than x. These cases will be handled naturally by the two-pointer approach without requiring additional logic.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n), where n is the number of nodes in the linked list, since each node is visited exactly once. The space complexity is O(1) because the solution modifies the list in place without using any additional data structures.

What Interviewers Usually Probe

Candidate effectively uses pointer manipulation to solve the problem.
Candidate correctly handles edge cases like empty lists or all nodes falling in one partition.
Solution demonstrates knowledge of linked-list traversal and node manipulation.

Common Pitfalls or Variants

Common pitfalls

Failing to preserve the relative order of nodes within each partition.
Incorrectly linking the 'less than x' partition to the 'greater than or equal to x' partition.
Not considering edge cases like empty lists or lists where all nodes fall into one partition.

Follow-up variants

Modify the problem to handle circular linked lists.
Partition the list in place using constant space.
Extend the problem by adding multiple partitions around different values.

FAQ

What is the most efficient way to partition a linked list?

The most efficient way is to use a two-pointer technique, which ensures the solution runs in O(n) time with constant space.

How can I handle edge cases like an empty list?

Edge cases like an empty list are naturally handled by the two-pointer approach, as no nodes will be processed.

What pattern is this problem based on?

This problem is based on linked-list pointer manipulation, where you manage pointers to reorder nodes into partitions.

How can I ensure the relative order is preserved?

You can ensure this by carefully separating nodes into two partitions and linking them while maintaining the original order in each partition.

Can I solve this problem without using extra space?

Yes, the problem can be solved in-place with O(1) space by manipulating the pointers of the existing nodes.

terminal

Solution

Solution 1: Simulation

We create two linked lists $l$ and $r$, one to store nodes less than $x$ and the other to store nodes greater than or equal to $x$. Then we concatenate them.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        l = ListNode()
        r = ListNode()
        tl, tr = l, r
        while head:
            if head.val < x:
                tl.next = head
                tl = tl.next
            else:
                tr.next = head
                tr = tr.next
            head = head.next
        tr.next = None
        tl.next = r.next
        return l.next

Continue Practicing

#82 remove duplicates from sorted list ii #61 rotate list #141 linked list cycle