Partition List
Problem Description
Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:
Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Example 2:
Input: head = [2,1], x = 2
Output: [1,2]
Constraints:
- The number of nodes in the list is in the range
[0, 200]. -100 <= Node.val <= 100-200 <= x <= 200
Solve it on LeetCode
Approaches
1. Two-Pass: Array-based Partition
Intuition:
The idea is to first convert the linked list into an array, partition the array into two parts, and then reconstruct the linked list. Although not the most efficient, it provides a clear separation of the partition logic.
Steps:
- Traverse through the original list and populate the values into an array.
- Partition the array into two separate lists - one containing elements less than
xand the other containing elements greater than or equal tox. - Traverse through these two lists and create a new linked list with the required order.
Code:
- Time Complexity: O(n), where n is the number of nodes in the linked list. Each node is visited exactly once.
- Space Complexity: O(n), because of the use of additional lists to store node values.
2. Two-Pointer: Single-pass LinkedList
Intuition:
Using two pointers, we directly manipulate the linked list to partition without extra space. This is achieved by creating two dummy head nodes representing partitions for values less than x and for values greater than or equal to x.
Steps:
- Initialize two dummy nodes
lessHeadandgreaterHeadto handle partitions. - Iterate through the list, linking nodes with values less than
xtolessand others togreater. - Connect the
lesslist with thegreaterlist. - The new head is the start of the
lesslist.
Code:
- Time Complexity: O(n), where n is the number of nodes in the linked list. Each node is visited exactly once.
- Space Complexity: O(1), no extra space except for pointers.