C++实现LeetCode(86.划分链表)

C++实现LeetCode(86.划分链表)完整攻略

问题描述

给定一个链表和一个特定值$x$，对于链表中的所有小于$x$的节点，排列在大于或等于$x$的节点之前。同时保留链表节点的初始相对顺序。

例如，给定的链表是1->4->3->2->5->2, 给定的值是$3$。那么，目标答案是1->2->2->4->3->5。

解决思路

首先，我们需要创建3个指针变量smallHead、smallTail、bigHead和bigTail用于分别指向小于$x$的节点的头、尾节点和大于等于$x$的节点的头、尾节点。

接着，我们遍历原链表，对于当前节点，如果它的值小于$x$，则把它链接在smallTail后面，并更新smallTail指针；如果大于等于$x`，则把它链接在bigTail后面，并更新bigTail指针。

最后，我们把smallTail链接到bigHead上，返回smallHead。

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* smallHead = new ListNode(0), *smallTail = smallHead;
        ListNode* bigHead = new ListNode(0), *bigTail = bigHead;
        while (head != nullptr) {
            if (head->val < x) {
                smallTail->next = head;
                smallTail = smallTail->next;
            }
            else {
                bigTail->next = head;
                bigTail = bigTail->next;
            }
            head = head->next;
        }
        smallTail->next = bigHead->next;
        bigTail->next = nullptr;
        return smallHead->next;
    }
};

示例说明

示例1：

输入: 1->4->3->2->5->2 和 x = 3
输出: 1->2->2->4->3->5
解释: 小于3的节点排列在大于等于3的节点之前，并且保留原始链表中每个节点的相对顺序。

示例2：

输入: 2->1 && x = 2
输出: 1->2
解释: 所有节点的值小于2，就按照原样排列。