題目一：

題目鏈接：

思路一：使用帶頭鏈表

1.構(gòu)建兩個新的帶頭鏈表，頭節(jié)點不存儲數(shù)據(jù)。
2.循環(huán)遍歷原來的鏈表。
3.小于x的尾插到第一個鏈表。
4.大于等于x尾插到第二個鏈表。
5.進行鏈表合并，注意第二個鏈表的尾的下一個需要置空防止成環(huán)。
6.free兩個頭之前需要保存新的滿足條件的單鏈表的頭。

#include <cstddef>
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* cur=pHead;//使用頭節(jié)點先開辟一個節(jié)點struct ListNode* lefthead,*lefttile;struct ListNode* righthead,*righttile;lefthead=lefttile=(ListNode*)malloc(sizeof(ListNode));righthead=righttile=(ListNode*)malloc(sizeof(ListNode));//遍歷鏈表分到左右兩個鏈表里面while(cur){ListNode* next=cur->next;//比cur小于等于if(cur->val<x){lefttile->next=cur;lefttile=lefttile->next;}else {righttile->next=cur;righttile=righttile->next;}cur=next;}//進行連接,有可能成環(huán)所以比x大的鏈表部分結(jié)尾需要置空。lefttile->next=righthead->next;righttile->next=NULL;struct ListNode* head=lefthead->next;//tile不可以釋放free(lefthead),free(righthead);return head;}
};

思路二：使用單鏈表

1.有一些地方需要更改。
2.兩個鏈表都有數(shù)據(jù)，鏈表初始化頭和尾是需要判斷的。
3.兩個鏈表都有數(shù)據(jù)那么跟上一個在鏈接上是差不多的。
4.當(dāng)其中一個鏈表沒有數(shù)據(jù)的時候返回另一個鏈表的第一個。

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code here//不開辟頭節(jié)點struct ListNode* leftfirst=NULL,*lefttile=NULL;struct ListNode* rightfirst=NULL,*righttile=NULL;//struct ListNode* cur=pHead;//不存在頭節(jié)點是需要判斷的。while(cur){struct ListNode* next=cur->next;if(cur->val<x){if(leftfirst==NULL){leftfirst=lefttile=cur;}else{lefttile->next=cur;lefttile=lefttile->next;}}else{if(rightfirst==NULL){rightfirst=righttile=cur;}else{righttile->next=cur;righttile=righttile->next;}}cur=next;}if(lefttile==NULL){return rightfirst;}if(righttile==NULL){return leftfirst;}lefttile->next=rightfirst;righttile->next=NULL; return leftfirst;}
};