程序员面试金典02.04 分割链表-中等

题目：

给你一个链表的头节点 head 和一个特定值 x，请你对链表进行分割，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要保留每个分区中各节点的初始相对位置。

解题思路

利用两个哑结点 left 和 right，遍历整个链表，其中 left 保存小于 x 的节点，right 保存大于或等于x的节点。

遍历结束，将两个链表在拼接起来。

注意，拼接前把 right 尾部置空。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// date 2023/10/09
func partition(head *ListNode, x int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    left, right := &ListNode{}, &ListNode{}
    p1, p2 := left, right
    
    for head != nil {
        if head.Val < x {
            p1.Next = head
            p1 = head
        } else {
            p2.Next = head
            p2 = head
        }
        head = head.Next
    }

    // 将 right 尾部封住
    if p2 != nil {
        p2.Next = nil
    }
    p1.Next = right.Next
    return left.Next
}