Note:

看到相对顺序，想到双指针同向而行

用两个指针作为新头，遍历整个list，将list分成两半，一半比target小，一半比target大。再将两段接在一起。

Key word:

将一个linked list以target为界分开，比target小的放左边，比target大的或相等的放右边

保持相对顺序

public class Solution {
  public ListNode partition(ListNode head, int target) {
    ListNode small = new ListNode(0);
    ListNode large = new ListNode(0);
    ListNode curSmall = small;
    ListNode curLarge = large;
    ListNode cur = head;
    while (cur != null) {
      if (cur.value < target) {
        curSmall.next = cur;
        curSmall = curSmall.next;
      } else {
        curLarge.next = cur;
        curLarge = curLarge.next;
      }
      cur = cur.next;
    }
		// connect two parts
    curSmall.next = large.next;

		//un-link the last node in large part;
    curLarge.next = null;
    return small.next;
  }
}

Complexity Analysis:

TC: O(N)

SC: O(1); Linked List operation都是in-place，并没有new 任何新的东西，只是指针的指向而已，所以是O(1);