[LeetCode] Partition List

Thought:
Find the first value that is equal or larger than x. Then put every smaller one before it.

Code:
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
     
        ListNode small = sentinel;
        ListNode large = head;
     
        while (large != null) {
            if (large.val >= x) break;
            small = small.next;
            large = large.next;
        }
     
        if (large == null) return sentinel.next;
     
        while (large.next != null) {
            ListNode tmp = large.next;
            if (tmp.val < x) {
                large.next = tmp.next;
                tmp.next = small.next;
                small.next = tmp;
                small = small.next;
            }else {
                large = large.next;          
            }

        }
     
        return sentinel.next;
    }
}