LeetCode 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.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        // The idea is: first get the last element and the length of the list
        // Then scan the whole list, if current node value < x, then go to the next node.
        // If current node value >=x, then move this node to the end of the list.
        // until  meet the length of the original list or 'cur' node meet 'last' node.
        if (head==null || head.next==null)
            return head;
        
        // Create a new node helper and put it before head.
        // Take helper as head.
        // In case the first element (head.val) is also >= x 
        ListNode helper = new ListNode(0);
        helper.next = head; // Used to save the result head.
        ListNode pre = helper;
        ListNode cur = pre.next;
        ListNode last = helper; // Used to get the last node

        int len = 0; //Length of the list
        
        // Calculate the length of the array
        // Save the last node to "last"
        while (last.next != null)
        {
            last = last.next;
            len++;
        }
        
        // Don't miss "cur!=last"
        // Otherwise, 'cur' node will be removed if "cur.val>=x"
        while (len>0 && cur!=last)
        {
            if (cur.val < x)
            {
                pre = pre.next;
                cur = cur.next;
            }
            else
            {
                pre.next = cur.next;
                cur.next = null;
                
                last.next = cur;
                cur = pre.next;
                
                last = last.next;
            }
            
            len--;
        }
        
        //Skip the new empty head
        return helper.next;
    }
}