對(duì)于一個(gè)鏈表，我們需要用一個(gè)特定閾值完成對(duì)它的分化姨蝴，使得小于等于這個(gè)值的結(jié)點(diǎn)移到前面焊傅，大于該值的結(jié)點(diǎn)在后面，同時(shí)保證兩類結(jié)點(diǎn)內(nèi)部的位置關(guān)系不變摊唇。
給定一個(gè)鏈表的頭結(jié)點(diǎn)head咐蝇，同時(shí)給定閾值val，請(qǐng)返回一個(gè)鏈表巷查，使小于等于它的結(jié)點(diǎn)在前有序，大于等于它的在后抹腿，保證結(jié)點(diǎn)值不重復(fù)。
測(cè)試樣例：
輸入：{1,4,2,5},3
輸出：{1,2,4,5}
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Divide {
public:
ListNode* listDivide(ListNode* head, int val) {
// write code here
if(NULL == head){
return NULL;
}
ListNode *left_a = NULL, *right_a = NULL;
ListNode *left_e = NULL, *right_e = NULL;
// 如果小于就放到左邊的鏈表旭寿，如果大于就放到右邊的鏈表
while(head != NULL){
if(head->val <= val){
if(NULL == left_a){
left_a = head;
left_e = head;
}else{
left_e->next = head;
left_e = head;
}
}else{
if(NULL == right_a){
right_a = head;
right_e = head;
}else{
right_e->next = head;
right_e = head;
}
}
head = head->next;
}
// 合并兩個(gè)鏈表
if(NULL != left_e){
if(NULL != right_a){
left_e->next = right_a;
right_e->next = NULL;
}
//cout<< 1 << endl;
return left_a;
}else{
//cout<< 2 << endl;
return right_a;
}
}
};
