86. Partition List

Problem Statement

Pattern: Pattern Array Partitioning

---

Solution

public ListNode partition(ListNode head, int x) {
	// iterators
	ListNode smaller = new ListNode(-1), bigger = new ListNode(-1);
	// heads
	ListNode smallHead = smaller, bigHead = bigger;
	
	while(head != null) {
		// append to smaller LL
		if(head.val < x) smaller = smaller.next = head;
		// append to bigger LL
		else bigger = bigger.next = head;
		// increment head
		head = head.next;
	}
	// set last node to null
	bigger.next = null;
	// connect end of smaller iterator and larger linked list
	smaller.next = bigHead.next;
	// return smallHead
	return smallHead.next;
}

Notes

• create 2 linked list heads and iterators, one for smaller than x numbers and one for larger than x
• connect both
• return small’s head