006、链表分割
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
//初始化两个带哨兵位头结点的链表，smailhead和bighead
ListNode* smailhead, *smailtail, *bighead, *bigtail;
smailhead = smailtail = (ListNode*)malloc(sizeof(ListNode));
bighead = bigtail = (ListNode*)malloc(sizeof(ListNode));
smailhead->next = nullptr;
bighead->next = nullptr;
ListNode* cur = pHead;
//遍历原链表
while (cur)
{
if (cur->val < x)
{
smailtail->next = cur;
smailtail = smailtail->next;
}
else
{
bigtail->next = cur;
bigtail = bigtail->next;
}
cur = cur->next;
}
//防止形成环
bigtail->next = nullptr;
//链接两个链表
smailtail->next = bighead->next;
pHead = smailhead->next;
free(smailhead);
free(bighead);
return pHead;
}
};