86. Partition List
Description
Given 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.
Constraints
Approach
Links
YouTube
Examples
Input:
head = 1 -> 4 -> 3 -> 2 -> 5 -> 2,
x = 3
Output: 1 -> 2 -> 2 -> 4 -> 3 -> 5
Solutions
// Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}/**
* Time complexity : O(N), where N is the number of nodes in the original linked
* list and we iterate the original list.
* Space complexity : O(1), we have not utilized any extra space, the point to
* note is that we are reforming the original list, by moving the original
* nodes, we have not used any extra space as such.
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null) return head;
ListNode smaller = new ListNode(0);
ListNode smallerHead = smaller;
ListNode greater = new ListNode(0);
ListNode greaterHead = greater;
while(head != null) {
if(head.val < x) {
smaller.next = head;
smaller = smaller.next;
} else {
greater.next = head;
greater = greater.next;
}
head = head.next;
}
greater.next = null;
smaller.next = greaterHead.next;
return smallerHead.next;
}
}Follow up
Traverse Linked List from middle to left-right order using recursion - GFG
Last updated
Was this helpful?