題目
解答
大致解析題目意思抵恋，就是把一個鏈表分成兩個部分，但是相對位置不變化嗤瞎，第一想法就是直接遍歷一次，分別使用兩個新鏈表存起來郑藏，最后拼接在一起衡查，就是需要的最后答案了。
1.創(chuàng)建左鏈表和右鏈表必盖，并創(chuàng)建記錄當(dāng)前位置的節(jié)點(diǎn)拌牲。2.取出原鏈表中的節(jié)點(diǎn)，被目標(biāo)參數(shù)比較歌粥，如果是小于目標(biāo)參數(shù)的塌忽，就放到左鏈表最后，并移動左鏈表當(dāng)前節(jié)點(diǎn)到下個節(jié)點(diǎn)失驶；如果是大于等于目標(biāo)參數(shù)的土居，就放到右鏈表最后，并移動右鏈表當(dāng)前節(jié)點(diǎn)到下個節(jié)點(diǎn)嬉探，最后移動原鏈表當(dāng)前節(jié)點(diǎn)到下個節(jié)點(diǎn)擦耀。3.重復(fù)步驟2拆挥，直到原鏈表所有的數(shù)據(jù)都被取完铭乾。4.最后拼接兩個鏈表，最后鏈表就是所需要的鏈表了
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
// 左邊鏈表頭
ListNode *leftHeadNode = new ListNode(0);
// 右邊鏈表頭
ListNode *rightHeadNode = new ListNode(0);
// 左邊鏈表的當(dāng)前位置
ListNode *leftCurrentNode = leftHeadNode;
// 右邊鏈表的當(dāng)前位置
ListNode *rightCurrentNode = rightHeadNode;
while (head != NULL) {
if (head->val < x) {
// 把小于x的節(jié)點(diǎn)放到左鏈表最后 并移動當(dāng)前節(jié)點(diǎn)到下個節(jié)點(diǎn)
leftCurrentNode->next = head;
leftCurrentNode = leftCurrentNode->next;
} else {
// 把大于等于x的節(jié)點(diǎn)放到右鏈表最后 并移動當(dāng)前節(jié)點(diǎn)到下個節(jié)點(diǎn)
rightCurrentNode->next = head;
rightCurrentNode = rightCurrentNode->next;
}
head = head->next;
}
// 拼接兩個列表
leftCurrentNode->next = rightHeadNode->next;
rightCurrentNode->next = NULL;
return leftHeadNode->next;
}
};
以上代碼時間復(fù)雜度為想鹰，創(chuàng)建了兩個新的鏈表胎围，空間復(fù)雜度為
吁系。
以上代碼時間復(fù)雜度已經(jīng)很低了德召，但是空間復(fù)雜度還有一定的優(yōu)化的空間，之前我們創(chuàng)建了兩個鏈表垮抗，現(xiàn)在考慮能不能就在原來的鏈表上操作氏捞，不創(chuàng)建新的鏈表呢？
這個我還沒想出來冒版，但是我們可以創(chuàng)建一個鏈表液茎，讓另外一部分在原來的鏈表上操作，最后拼接起來辞嗡。
1.創(chuàng)建左鏈表和原鏈表的父節(jié)點(diǎn)捆等，并創(chuàng)建記錄當(dāng)前位置的節(jié)點(diǎn)。2.取出原鏈表中的節(jié)點(diǎn)续室，被目標(biāo)參數(shù)比較栋烤，如果是小于目標(biāo)參數(shù)的，就放到左鏈表最后挺狰，移動左鏈表當(dāng)前節(jié)點(diǎn)到下個節(jié)點(diǎn)明郭，并把當(dāng)前節(jié)點(diǎn)從原鏈表中刪除；如果是大于等于目標(biāo)參數(shù)的丰泊，直接移動原鏈表當(dāng)前節(jié)點(diǎn)到下個節(jié)點(diǎn)薯定。3.重復(fù)步驟2，直到原鏈表所有的數(shù)據(jù)都被取完瞳购。4.最后拼接兩個鏈表话侄，最后鏈表就是所需要的鏈表了
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
// 左邊鏈表頭
ListNode *leftHeadNode = new ListNode(0);
// 原節(jié)點(diǎn)的父節(jié)點(diǎn)
ListNode *fatherHeadNode = new ListNode(0);
// 為了讓第一個節(jié)點(diǎn)擁有父節(jié)點(diǎn) 刪除節(jié)點(diǎn)的時候容易一點(diǎn) 所以為原鏈表設(shè)置一個父節(jié)點(diǎn)
fatherHeadNode->next = head;
// 左邊鏈表的當(dāng)前位置
ListNode *leftCurrentNode = leftHeadNode;
// 原鏈表的當(dāng)前位置
ListNode *headCurrentNode = fatherHeadNode;
while (headCurrentNode->next != NULL) {
// 判斷當(dāng)前的值
if (headCurrentNode->next->val < x) {
// 把小于x的節(jié)點(diǎn)放到左鏈表最后 并移動當(dāng)前節(jié)點(diǎn)到下個節(jié)點(diǎn)
leftCurrentNode->next = headCurrentNode->next;
leftCurrentNode = leftCurrentNode->next;
// 刪除當(dāng)前的節(jié)點(diǎn)
headCurrentNode->next = headCurrentNode->next->next;
leftCurrentNode->next = NULL;
} else {
// 當(dāng)前節(jié)點(diǎn)不變 移動當(dāng)前節(jié)點(diǎn)到下個節(jié)點(diǎn)
headCurrentNode = headCurrentNode->next;
}
}
// 拼接兩個列表
leftCurrentNode->next = fatherHeadNode->next;
return leftHeadNode->next;
}
};
以上代碼時間復(fù)雜度為，但是只創(chuàng)建了一個新的鏈表学赛，雖然空間復(fù)雜度還是為
年堆，但是在使用的空間上比之前的算法減少了一點(diǎn)。
在朋友的提示下盏浇，終于想到了時間復(fù)雜度的解法变丧，說起來也簡單，之前怎么就沒有想到呢缠捌？
原理就是通過和目標(biāo)參數(shù)的比較锄贷，把小于目標(biāo)參數(shù)的放在鏈表的前面，把大于等于目標(biāo)參數(shù)的放在鏈表的后面曼月，這樣相當(dāng)于鏈表就被分割成了兩部分谊却，最后把兩部分拼接起來就好了
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
// 左邊鏈表頭
ListNode *leftHeadNode = new ListNode(0);
// 右邊鏈表頭
ListNode *rightHeadNode = new ListNode(0);
rightHeadNode->next = head;
// 左邊鏈表的當(dāng)前位置
ListNode *leftCurrentNode = leftHeadNode;
// 右邊鏈表的當(dāng)前位置
ListNode *rightCurrentNode = rightHeadNode;
while (rightCurrentNode->next != NULL) {
if (rightCurrentNode->next->val < x) {
// 移除這個點(diǎn) 并重新拼接原來的節(jié)點(diǎn)
leftCurrentNode->next = rightCurrentNode->next;
leftCurrentNode = leftCurrentNode->next;
rightCurrentNode->next = rightCurrentNode->next->next;
} else {
rightCurrentNode = rightCurrentNode->next;
}
}
leftCurrentNode->next = rightHeadNode->next;
return leftHeadNode->next;
}
};
以上代碼時間復(fù)雜度為，空間復(fù)雜度還是為
哑芹。
