題目：
現有一鏈表的頭指標 ListNode* pHead，給一定值x，撰寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的資料順序，回傳重新排列后的鏈表的頭指標，
題目分析：
解決這個問題采用的方法是：
把比x小的值插入到一個鏈表，
把比x大的值插入到一個鏈表，
再把兩個鏈表連接到一起，
代碼實作：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = pHead;
while(cur)
{
if(cur->val<x)
{
lessTail->next = cur;
lessTail = cur;
}
else
{
greaterTail->next = cur;
greaterTail = cur;
}
cur = cur->next;
}
//切記把最后一個的next置成空，
greaterTail->next = NULL;
lessTail->next = greaterHead ->next;
struct ListNode* head = lessHead->next;
free(lessHead);
free(greaterHead);
return head;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299934.html
標籤：其他