706230. Partition a Linked List around a given value
Partition a Linked List around a given value
Summary
Given a singly linked list and an integer x, partition the linked list such that all nodes less than x are moved to the left side of the linked list, while all nodes greater than or equal to x are moved to the right side. The relative order of elements in the same group should remain unchanged.
Detailed Explanation
To solve this problem, we can use two pointers, one for the head of the new list and one for the current node in the original list. We iterate through the original list until we find a node that is greater than or equal to x, then we move it to the right side. The nodes less than x are moved to the left side.
Here's a step-by-step breakdown of the solution:
- Initialize two pointers,
headandprev, both pointing toNULL. These will be used to build the new list. - Iterate through the original linked list until you find a node that is greater than or equal to
x. - When you find such a node, move it to the right side of the new list by updating the
nextpointer of the previous node (orheadif this is the first node) and setting itsnextpointer to the current node. - Repeat step 2 until the end of the original list is reached.
- The nodes less than
xare moved to the left side, so return theheadof the new list.
Time complexity: O(n), where n is the number of nodes in the linked list. We only iterate through the list once, so the time complexity is linear. Space complexity: O(1), as we only use a few extra variables to store the pointers.
Optimized Solutions
Java
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode partition(ListNode head, int x) {
ListNode beforeStart = null;
ListNode beforeEnd = null;
ListNode afterStart = null;
ListNode afterEnd = null;
while (head != null) {
if (head.val < x) {
if (beforeStart == null) {
beforeStart = head;
beforeEnd = beforeStart;
} else {
beforeEnd.next = head;
beforeEnd = beforeEnd.next;
}
} else {
if (afterStart == null) {
afterStart = head;
afterEnd = afterStart;
} else {
afterEnd.next = head;
afterEnd = afterEnd.next;
}
}
head = head.next;
}
if (beforeStart == null) {
return afterStart;
}
beforeEnd.next = afterStart;
return beforeStart;
}
}