分隔链表

问题描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

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

思路

借助了两个vector。

• 若是链表为空：直接返回nullptr即可。
• 链表不为空：遍历链表的过程中，将节点值小于x的存到一个vector中，将值大于等于x的存到一个vector中。
• 利用两个vector生成两个链表。

• 根据不同情况将两个链表拼接起来。

  小于x的链表为空，那么返回大于x链表的头节点即可
  大于等于x的链表为空，那么返回小于x链表的头节点即可
  两个都不空，将大于等于x的链表拼接到小于x的链表的后面
  两个链表都为空，即链表为空，在最开始特判过了。

题解

class Solution {
public:
    vector<int> tmp1;
    vector<int> tmp2;
    ListNode *head1;
    ListNode *head2;
    ListNode *ret;
    ListNode *buildList(vector<int> vec, ListNode *&node) {
        int n = vec.size();
        ListNode *p = nullptr;
        for (int i = 0; i < n; i++) {
            if (p == nullptr) {
                p = new ListNode(vec[i]);
                node = p;
            } else {
                p->next = new ListNode(vec[i]);
                p = p->next;
            }
        }
        return node;
    }

    ListNode *partition(ListNode *head, int x) {
        if (head == nullptr)
            return nullptr;
        ListNode *cur = head;
        while (cur != nullptr) {
            if (cur->val < x) tmp1.push_back(cur->val);
            else tmp2.push_back(cur->val);
            cur = cur->next;
        }
        int n1=tmp1.size();
        int n2 =tmp2.size();
        if(n1!=0) head1=buildList(tmp1,head1);
        if(n2!=0) head2=buildList(tmp2,head2);
        if(n1==0&&n2!=0) ret = head2;
        else if(n2==0&&n1!=0) ret =  head1;
        else {
            ListNode *tail=head1;
            while (tail->next!= nullptr){
                tail=tail->next;
            }
            tail->next=head2;
            ret = head1;
        }
        return ret;
    }
};