Partition List

1public ListNode partition(ListNode head, int x) {
2    ListNode lessHead = new ListNode(0);
3    ListNode greaterHead = new ListNode(0);
4
5    ListNode less = lessHead;
6    ListNode greater = greaterHead;
7
8    // Partition list into less and greater lists
9    while (head != null) {
10        if (head.val < x) {
11            // Append to less list
12            less.next = head;
13            less = less.next;
14        } else {
15            // Append to greater list
16            greater.next = head;
17            greater = greater.next;
18        }
19        head = head.next;
20    }
21
22    // Important: break any existing pointers to ensure no cycles
23    greater.next = null;
24    less.next = greaterHead.next;
25
26    return lessHead.next;
27}