无心插柳柳成荫


思路：
新建两个头来记录两种类型的节点，最后连起来

代码：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    newhead1 := &ListNode{0, nil}
    newhead2 := &ListNode{0, nil}
    cur := head
    rec1 := newhead1
    rec2 := newhead2
    for cur != nil {
        if cur.Val < x {
            newhead1.Next = cur
            newhead1 = newhead1.Next
        } else {
            newhead2.Next = cur
            newhead2 = newhead2.Next
        }
        cur = cur.Next
    }
    newhead1.Next = rec2.Next
    newhead2.Next = nil

    return rec1.Next

}