0086.分隔链表

https://leetcode.cn/problems/partition-list/

方法一：遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
	dummy1, dummy2 := &ListNode{}, &ListNode{}
	p1, p2 := dummy1, dummy2
	for ; head != nil; head = head.Next {
		if head.Val < x {
			p1.Next, p1 = head, head
		} else {
			p2.Next, p2 = head, head
		}
	}
	p1.Next, p2.Next = dummy2.Next, nil
	return dummy1.Next
}