🥈86.分隔链表

🥈Medium

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

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

示例：

输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5

题解

要想让链表在x处分隔，可以维护两个链表，一个small，存储所有小于x的节点，一个large，存储所有大于x的节点。遍历完原链表之后，只要small链表尾节点指向large头结点即可。

思路很清晰了，但是实现上还需要注意设置哑节点，设smallHead和largeHead分别为两个链表的哑节点，即它们的next指针指向链表头节点，这样做是为了方便处理头结点为空的边界条件。同时设置small和large节点指向当前链表末尾节点。开始时，smallHead=small，largeHead=large。随后，从前向后遍历链表，判断当前链表节点值是否小于x，如果小于就将small的next指针指向该节点，否则将large的next指针指向该节点。

遍历结束后，将large的next置空，这是因为当前节点复用的是原链表的节点，而其next指针可能指向一个小于x的节点，需要切断这个引用。同时将small的next指针指向largeHead的next指针指向的节点，即真正意义上的large链表头结点，最后返回smallHead的next指针。

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        largeHead = ListNode()
        smallHead = ListNode()
        small = smallHead
        large = largeHead
        cur = head
        while cur:
            if cur.val < x:
                small.next = cur
                small = small.next
            else:
                large.next = cur
                large = large.next
            cur = cur.next
        small.next = largeHead.next
        large.next = None
        return smallHead.next

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    let small = new ListNode(0);
    const smallHead = small;
    let large = new ListNode(0);
    const largeHead = large;
    while (head !== null) {
        if (head.val < x) {
            small.next = head;
            small = small.next;
        } else {
            large.next = head;
            large = large.next;
        }
        head = head.next;
    }
    large.next = null;
    small.next = largeHead.next;
    return smallHead.next;
};