题目描述

leetcode链接

解法分析

这道题本身并不难，也基本没有什么陷阱，多做几次链表题目后应该非常快。我是第一次一把过中级题目，还有点小兴奋。

唯一可能要注意的就两点：

1. 链表记得加哑节点；
2. 注意右侧的链表最后的next要置null。

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if (!head) {
            return nullptr;
        }

        auto leftHead = make_shared<ListNode>(0);
        ListNode *leftCur = leftHead.get();
        auto rightHead = make_shared<ListNode>(0);
        ListNode *rightCur = rightHead.get();

        ListNode *pNode = head;
        while (pNode) {
            if (pNode->val < x) {
                leftCur->next = pNode;
                leftCur = leftCur->next;
            } else {
                rightCur->next = pNode;
                rightCur = rightCur->next;
            }
            pNode = pNode->next;
        }

        leftCur->next = rightHead->next;
        rightCur->next = nullptr;

        return leftHead->next;
    }
};