package com.example.medium;

/**
 * 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.
 * @author FuPing
 *
 */
public class Partition {

    public class ListNode {
         int val;
         ListNode next;
         ListNode(int x) { val = x; }
     }
    public ListNode partition(ListNode head, int x) {
        ListNode lessList = null,moreList = null;
        ListNode lessTail = null,moreTail = null;
        while(head != null){
            if(head.val < x){
                if(lessList == null){
                    lessList = head;
                    lessTail = head;
                }else{
                    lessTail.next = head;
                    lessTail = lessTail.next;
                }
            }else{
                if(moreList == null){
                    moreList = head;
                    moreTail = head;
                }else{
                    moreTail.next = head;
                    moreTail = moreTail.next;
                }
            }
            head = head.next;
        }
        if(lessList == null)return moreList;
        lessTail.next = moreList;
        if(moreList != null)moreTail.next = null;
        return lessList;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }

}