描述

在一个单链表中，给定一个值X，根据X将链表分割成两部分，小于X的节点在大于等于X节点的左面。

在分割成的两部分要保持数据相对位置不变。

输入：

​ 1->4->3->2->5->2

输出：

​ 1->2->2->4->3->5

分析

定义两个链表，一个存放节点值小于X值的节点，另一个存放节点值大于等于X值的节点。遍历原始链表，将每个节点从原始链表中拆除，根据以上规则分别存放到对应的链表。

实现

ListNode* partition(ListNode* head, int x)
{
    ListNode hLeft(-1);
    ListNode hRight(-1);
    
    ListNode *pCurLeft = &hLeft;
    ListNode *pCurRight = &hRight;
    
    for(ListNode *cur=head; cur; cur=cur->next) {
        if (cur->val < x) {
            pCurLeft->next = cur;
            pCurLeft = cur;
        }
        else {
            pCurRight->next = cur;
            pCurRight = cur;
        }
    }
    pCurLeft->next = hRight.next;
    pCurRight->next = nullptr;
    
    return hLeft.next;
}

时间复杂度O(n)，空间复杂度O(1)。

代码在这儿