Algorithm
Initialize two dummy nodes: lessHead and highHead to serve as heads for two separate lists, one for nodes with values less than x and one for nodes with values greater than or equal to x.
Initialize pointers less and high to keep track of the tail of the two lists respectively.
Iterate through the original linked list (head) using a temporary pointer temp.
For each node in the original list:
If the value of the current node (temp.val)
is less than x, append it to the less list.
If the value of the current node is greater
than or equal to x, append it to the high
list.
Connect the tail of the less list to the head of the high list.
Return the head of the less list, which now contains the partitioned linked list.
Code
public ListNode partition(ListNode head, int x) {
ListNode lessHead = new ListNode(0);
ListNode highHead = new ListNode(0);
ListNode less = lessHead, high = highHead;
ListNode temp = head;
while(temp!=null){
if(temp.val<x){
less.next = new ListNode(temp.val);
less = less.next;
}
else{
high.next = new ListNode(temp.val);
high = high.next;
}
temp = temp.next;
}
less.next = highHead.next;
return lessHead.next;
}
}
Thanks for reading🥰.
Feel free to comment🖌️ and like the post💓
Follow for more 🤝 && Happy Coding🚀👩💻
Don’t forget to check-out my other socials😍:
Github
Hashnode
Medium
Twitter(X)
