Skip to content

Instantly share code, notes, and snippets.

@InterviewBytes InterviewBytes/ListNode.java Secret
Created Jun 9, 2017

Embed
What would you like to do?
Partition linkedlist such that all nodes less than x come before nodes greater than or equal to x.
package com.interviewbytes.linkedlists;
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
package com.interviewbytes.linkedlists;
public class Partition {
public ListNode partition(ListNode head, int x) {
ListNode lesserSentinel = new ListNode(0);
ListNode greaterSentinel = new ListNode(0);
ListNode currentLesser = lesserSentinel;
ListNode currentGreater = greaterSentinel;
while (head != null) {
if (head.val < x) {
currentLesser.next = head;
currentLesser = currentLesser.next;
} else {
currentGreater.next = head;
currentGreater = currentGreater.next;
}
head = head.next;
}
currentLesser.next = greaterSentinel.next;
currentGreater.next = null;
return lesserSentinel.next;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.