题解 | #链表分割#
链表分割
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70
/*
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
/*思路：小于的跟着一个哨兵头，非小于的跟着另一个哨兵头，第一个哨兵头的结尾连着另外一个哨兵头的next，*/
ListNode* guard = (ListNode*)malloc(sizeof(ListNode));/*两个哨兵头，分别代表小于x和不小于x的哨兵头*/
ListNode* guard2 = (ListNode*)malloc(sizeof(ListNode));
guard->next = NULL;
guard2->next = NULL;
ListNode* guard_cur = guard;/*统计小于x的节点*/
ListNode* guard_cur2 = guard2;/*统计不小于x的节点*/
ListNode* cur = pHead;/*统计所有节点*/
while(cur)
{
if(cur->val < x)
{
guard_cur->next = cur;
guard_cur = guard_cur->next;
}
else
{
guard_cur2->next = cur;
guard_cur2 = guard_cur2->next;
}
cur = cur->next;
}
guard_cur->next = NULL;
guard_cur2->next = NULL;
guard_cur->next = guard2->next;
pHead = guard->next;
free(guard);
free(guard2);
return pHead;
}
};