[数据结构与算法]LeetCode 刷题系列 -- 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-list
?

思路：

定义两个指针 small 与 big ，遍历链表 若是当前节点? 小于 x 时，将节点放到 small 链表结尾；若是当前节点大于等于 x 时，将节点放到 big 链表的结尾?；

c++?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode smallNode = ListNode();
        ListNode bigNode = ListNode();

        ListNode* smallNodePtr = &smallNode;
        ListNode* bigNodePtr = &bigNode;
        
        ListNode* currentSmallPtr = smallNodePtr;
        ListNode* currentBigPtr = bigNodePtr;

        auto current = head;

        while(current!=nullptr) {
            if(current->val < x) {
                currentSmallPtr->next = current;
                current = current->next;
                currentSmallPtr = currentSmallPtr->next;
            } else {
                currentBigPtr->next = current;
                current = current->next;
                currentBigPtr = currentBigPtr->next;
            }
        }
        currentBigPtr->next = nullptr;
        currentSmallPtr->next = bigNodePtr->next;

        return smallNodePtr->next;
    }
};