86. 分隔链表（中等系列）

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

你应当保留两个分区中每个节点的初始相对位置。

示例 1：
在这里插入图片描述
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：

链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200

public ListNode partition(ListNode head, int x) {// 初始化左半部分链表的头和尾节点ListNode leftHead = null, leftTail = null;// 初始化右半部分链表的头和尾节点ListNode rightHead = null, rightTail = null;// 用于保存下一个节点的指针ListNode next = null;// 遍历链表节点while (head != null) {// 保存当前节点的下一个节点next = head.next;// 断开当前节点与下一个节点的连接head.next = null;// 判断节点值与 x 的大小关系if (head.val < x) {if (leftHead == null) {leftHead = head;} else {leftTail.next = head;}leftTail = head;} else {if (rightHead == null) {rightHead = head;} else {rightTail.next = head;}rightTail = head;}// 移动到下一个节点head = next;}// 如果左半部分链表为空，直接返回右半部分链表if (leftHead == null) {return rightHead;}// 将左半部分链表的尾节点与右半部分链表的头节点连接起来leftTail.next = rightHead;// 返回整合后的链表return leftHead;
}