leetcode-86. 分割链表

题目描述

image-20200105151918018.png

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;
    }
};

评论

暂无评论