86. Partition List
Last updated
Last updated
// 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;
}
}