問題描述

給定一個鏈表和一個特定值 x，對鏈表進行分隔，使得所有小於 x 的節點都在大於或等於 x 的節點之前。你應當保留兩個分區中元素的初始相對順序。

示例:

輸入: head = 1->4->3->2->5, x = 2
輸出: 1->2->4->3->5

解法一

解題思路: 使用兩個指針分別指向小於x和大於等於x的節點，遍歷鏈表，將小於x的節點連接到前一個小於x的節點，將大於等於x的節點連接到前一個大於等於x的節點。最後將兩個鏈表連接起來。

/*
 * @lc app=leetcode.cn id=725 lang=javascript
 *
 * [725] 分隔鏈表
 */

// @lc code=start
function splitListToParts(head, k, x) {
    let dummy1 = new ListNode(0);
    let dummy2 = new ListNode(0);
    let cur1 = dummy1;
    let cur2 = dummy2;
    let node = head;
    while (node) {
        if (node.val < x) {
            cur1.next = node;
            cur1 = cur1.next;
        } else {
            cur2.next = node;
            cur2 = cur2.next;
        }
        node = node.next;
    }
    cur1.next = null;
    cur2.next = null;
    let parts = [];
    for (let i = 0; i < k; i++) {
        let part = dummy1.next;
        dummy1.next = null;
        if (i < k - 1) {
            dummy1.next = cur2.next;
            cur2.next = null;
        }
        parts.push(part);
        dummy1 = cur2;
        cur2 = new ListNode(0);
    }
    return parts;
}
// @lc code=end