// Path: src/commons/datastructures/ListNode.java
// public class ListNode {
//     public int val;
//     public ListNode next;
//     public ListNode(int x) {
//         val = x;
//         next = null;
//     }
// 
//     @Override
//     public String toString() {
//         return "ListNode{" +
//                 "val=" + val +
//                 '}';
//     }
// }


import commons.datastructures.ListNode;
package PartitionList;


/**
 * User: Danyang
 * Date: 1/26/2015
 * Time: 15:26
 *
 * 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.
 */
public class Solution {
    /**
     * diagram
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
// Path: src/commons/datastructures/ListNode.java
// public class ListNode {
//     public int val;
//     public ListNode next;
//     public ListNode(int x) {
//         val = x;
//         next = null;
//     }
// 
//     @Override
//     public String toString() {
//         return "ListNode{" +
//                 "val=" + val +
//                 '}';
//     }
// }


// Path: src/PartitionList/Solution.java
import commons.datastructures.ListNode;

package PartitionList;


/**
 * User: Danyang
 * Date: 1/26/2015
 * Time: 15:26
 *
 * 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.
 */
public class Solution {
    /**
     * diagram
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        ListNode d1 = new ListNode(0);  // dummy