/**
 * class ListNode {
 *   public int value;
 *   public ListNode next;
 *   public ListNode(int value) {
 *     this.value = value;
 *     next = null;
 *   }
 * }
 */
public class Solution {
  public ListNode partition(ListNode head, int target) {
    // write your solution here
    if(head == null || head.next == null) {
      return head;
    }
    ListNode leftDummy = new ListNode(0);
    ListNode left = leftDummy;
    ListNode rightDummy = new ListNode(0);
    ListNode right = rightDummy;

    while(head != null) {
      if (head.value < target) {
        left.next = head;
        left = left.next;
      } else {
        right.next = head;
        right = right.next;
      }
      head = head.next;
    }
    left.next = rightDummy.next;
    right.next = null;

    return leftDummy.next;
  }
}

思路：两个dummy，两个支针， 循环比较连接。 注意断尾。