Partition List

LeetCode Q 86 - Partition List

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.

Example:
Input: head = 1->4->3->2->5->2, x = 3 ; Output: 1->2->2->4->3->5

Solution

Code:

public ListNode partition(ListNode head, int x) {
	
	if (head == null) return head;

	ListNode smallHead = new ListNode (-1), small = smallHead;
	ListNode largeHead = new ListNode (-1), large = largeHead;

	while (head != null) {
		if (head.val < x) {
			small.next = head;
			small = small.next;
		} else {
			large.next = head;
			large = large.next;
		}

		head = head.next;
	}
	
	small.next = largeHead.next;
	large.next = null;
	
	return smallHead.next;
}