给出一个长度为 n 的单链表和一个值 x ，请返回一个链表的头结点，要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧，并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。

复杂度要求：

时间  O（n）

空间  O（1）

思路：新建一个比x小的部分的头，再建一个比x大的部分的头，然后遍历把他们分别放到小的部分和大的部分。然后两个部分连起来。返回小的头的next。

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param x int整型 
  * @return ListNode类
*/
func partition( head *ListNode ,  x int ) *ListNode {
    // write code here
    if head == nil {
        return head
    }
    less := new(ListNode)
	newHead := less
	large := new(ListNode)
	newLarge := large
	for head != nil {
		if head.Val < x {
			less.Next = head
			less = less.Next
		} else {
			large.Next = head
			large = large.Next
		}
		head = head.Next
        less.Next = nil
        large.Next = nil
	}
	less.Next = newLarge.Next
	return newHead.Next
}