算法1
暴力枚举
两个数组分别把小于x和其他值存进去,然后再用两个数组的值修改原先链表的值。内存消耗大,比较慢。
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> v1,v2; //开两个数组存储值
ListNode* partition(ListNode* head, int x) {
if(!head) return head;
auto p=head;
while(p)
{
if(p->val<x) v1.push_back(p->val);
else v2.push_back(p->val);
p=p->next;
}
p=head;
int cnt=0,n1=v1.size(),n2=v2.size();
while(p)
{
if(cnt<n1) p->val=v1[cnt];
else p->val=v2[cnt-n1];
p=p->next;
cnt++;
}
return head;
}
};
算法2
开两个链表
把小于x的点接在p1,其他点接在p2,最后把p1和p2连起来,最后要把p2->next=NULL,不然会报错。速度更快,内存占用小。
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> v1,v2;
ListNode* partition(ListNode* head, int x) {
if(!head) return head;
ListNode *p1=new ListNode(-1); //p1头结点
ListNode *p1head=p1;
ListNode *p2=new ListNode(-1); //p2头结点
ListNode *p2head=p2;
while(head)
{
if(head->val<x)
{
p1->next=head;
p1=p1->next;
}
else
{
p2->next=head;
p2=p2->next;
}
head=head->next;
}
p2->next=NULL; //p2->next指向空
p1->next=p2head->next;
return p1head->next;
}
};