做到时间复杂度O(N),空间负载度O(1),并保持其稳定性。即,改变之后的链表其相对顺序是不变的。
需要使用到六个变量
思路:
将主链表拆分成三个小链表,分别为小于部分,等于部分,大于部分。最后将三个链表串联起来。
SH指向小于部分的头结点,ST指向尾结点。
EH指向等于部分的头结点,ET指向尾结点。
BH指向大于部分的头结点,BT指向尾结点。
上代码:
//链表划分-进阶
//做到时间复杂度O(N),空间负载度O(1),并保持其稳定性。即,改变之后的链表其相对顺序是不变的。
#include <bits/stdc++.h>
using namespace std;
struct Node{
int val;
Node* next;
};
class Solution {
public:
Node* head;
Node* end;
int len;
Solution(){
//咋们将链表设置为有头结点的.就是第一个结点是没有数据的那种
Node* node = new Node();
node->next = NULL;
head = node;
end = node;
len = 0;
}
/**
* @param x int整型
*/
void partition(int x) {
//六个变量, 准备划分成三个部分。
Node* SH = NULL;
Node* ST = NULL;
Node* EH = NULL;
Node* ET = NULL;
Node* BH = NULL;
Node* BT = NULL;
Node* p = head->next;
while(p != NULL){
if(p->val > x){
//如果当前结点的数据大于给定数
if(BH == NULL){
//说明<部分没有结点,需要开始初始化
BT = p;
BH = p;
}else{
//如果大于部分已经有结点了,只需继续链接就可以了。
BT->next = p;
BT = p;
}
}else if(p->val < x){
//如果当前结点的数据小于给定数
if(SH == NULL){
SH = p;
ST = p;
}else{
ST->next = p;
ST = p;
}
}else{
//如果当前结点数据等于给定数
if(EH == NULL){
EH = p;
ET = p;
}else{
EH->next = p;
EH = p;
}
}
p = p->next;
}
//开始链接三部分链表
//需要考虑如果小于部分没有结点的情况
if(ST == NULL) {
SH = EH;
}else{
//说明小于部分的链表是有结点
ST->next = EH;
}
//等于部分肯定要有的。
ET->next = BH;
//需要将大于部分的链表的最后一个结点后继设为空,否则会在中间有环
if(BT != NULL){
BT->next = NULL;
}
head->next = SH;
}
Node* push(int i){
Node* node = new Node();
node->val = i;
end->next = node;
end = node;
len++;
}
void show(){
Node* p = head->next;
while(p != NULL){
cout<<p->val<<" ";
p = p->next;
}
cout<<endl;
}
};
int main(void){
Solution s;
//输入多少的数据
int n;
cin>>n;
//开始输入数据
while(n--){
int a;
cin>>a;
s.push(a);
}
//输出分界之前的链表
cout<<"输出分界之前的链表"<<endl;
s.show();
//输入分界的数字
int k;
cout<<"输入分界的数字:"<<endl;
cin>>k;
s.partition(k);
cout<<"开始输出分界之后的数据"<<endl;
s.show();
return 0;
}
cs