划分链表

---

题目链接

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

给你一个链表的头节点 head 和一个特定值 x，请你对链表进行分隔，使得所有 0 小于 x 的节点都出现在 大于或等于 x 的节点之前，你应当保留两个分区中每个节点的初始相对位置

思路分析

用 head 指针遍历每个节点，将遍历当前节点的 next 域置空，并判断当前节点的值与 x 的关系，同时用 next 指针记录 head 下一轮遍历要跳转的位置

分别建立 < x 的链表和 >= x 的链表，完成节点的挂接，最后链接两个链表

节点挂接完成后需要判断空链表的情况，否则会出现空指针异常

代码实现

class Solution {
    public ListNode partition(ListNode head, int x) {
        // 分别定义 小于 x 的链表和大于等于 x 的链表，最后二者链接
        ListNode leftHead = null;
        ListNode leftTail = null;
        ListNode rightHead = null;
        ListNode rightTail = null;

        // 记录下一个节点，在节点挂接后 head 继续遍历链表
        ListNode next = null;

        while (head != null) {
            next = head.next;
            // 先将当前遍历节点的 next 置空，用于划分链表
            head.next = null;

            // 判断当前节点是 < x 还是 >= 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 指针到下一个节点，进入下一轮的遍历
            head = next;
        }

        // < x 的链表为空，返回 >= x 的链表
        if (leftHead == null) {
            return rightHead;
        }

        // 两个链表都不为空，链接两个链表
        leftTail.next = rightHead;
        return leftHead;
    }
}