[LeetCode] 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.

 解题思路：
用两个指针，一个指针遍历整个list，一个指针来指向当前小于x的最后一个node
这样每次找到一个新的node小于x，则把此node移到当前最后一个小于x的后面.
考虑到初始没有小于x的node,则增加一个dummy node 在开头，作为最开始的最后一个小于x的node

Java Code:

public ListNode partition(ListNode head, int x) {
        ListNode safeHead = new ListNode(0);
        safeHead.next = head;
        ListNode prev = safeHead;
        ListNode p = prev;
        
        while(p.next != null && p.next.val < x){
                p = p.next;
                prev = p;
        }
        
        while(p.next != null){
            if(p.next.val < x){          
                ListNode tmp = p.next;
                p.next = p.next.next;
                tmp.next = prev.next;
                prev.next = tmp;
                prev = prev.next;
                
              }else{
                p = p.next;
             }
        }
        
        return safeHead.next;
    }