题解 | #链表分割#
链表分割
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70
1. 创建两个哨兵结点guard1，guard2；
2. 遍历链表将数值小于x的结点依次连接到guard2后面；其他结点依次链接到guard1后面。
3.最后，将guard1再链接到guard2后面
例1：与9比较
例2：与4比较
虽然用的是C++的模块，但语法都是C的。
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
//为原链表添加头结点 guard1
struct ListNode* guard1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(guard1);
//返回链表的头结点guard2
struct ListNode* guard2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(guard2);
struct ListNode* prev = guard1;
prev->next = pHead;
struct ListNode* cur = pHead;
struct ListNode* tail = guard2;
while (cur)
{
if (cur->val < x)
{
prev->next = cur->next;
//cur->next = NULL;
tail->next = cur;
tail = cur;
cur = prev->next;
}
else
{
prev = prev->next;
cur = cur->next;
}
}
tail->next = guard1->next;
return guard2->next;
}
};
