86-分隔链表

LeetCode 86. Partition List

LeetCode-86

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

method

题意：小于x的节点在前，大于等于x的节点在后

一个指针head负责遍历，另外两个指针small和large记录满足条件的节点

ListNode* partition(ListNode* head, int x) {
    ListNode *small = new ListNode(0);
    ListNode *large = new ListNode(0);
    ListNode *smallHead = small;    // 记录small头
    ListNode *largeHead = large;    // 记录large头
    while (head) {
        if (head->val < x) {
            small->next = head;
            small = small->next;
        }
        else {
            large->next = head;
            large = large->next;
        }
        head = head->next;
    }
    small->next = largeHead->next;  // small链接large
    large->next = nullptr;          // 断开large
    return smallHead->next;
}