我们上点强度，如果要保留各分区中节点的初始相对位置，应该怎么办？
此时想法就是，创建两个lesshead和morehead链表指针，把小于x的节点放在lesshead链表里，把大于等于x的节点放在morehead链表里，最后再将两个链表链接起来
但是这里只用指针的话，会遇到空链表的情况要分类讨论，比较麻烦，所以这里我们可以创建哨兵位，用带头链表会比较方便
但如果你是这样写的话，可能会遇到以下报错，这是为什么呢？
这是因为，你创建的哨兵位中next没有初始化，所以要将其置为NULL
在判断的时候，如果cur指向的值小于x，则链接到lesstail上，反之，则链接到moretail上。不过，此时要注意，链接完以后，应该及时将尾部节点next置为NULL，否则后续可能会出现环状链表
链接完两个链表后，记得要把哨兵位的空间给释放掉
最终代码如下：
struct ListNode* partition(struct ListNode* head, int x) { struct ListNode* lesshead , *lesstail, *morehead, *moretail; lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode)); lesshead->next = NULL; morehead = moretail = (struct ListNode*)malloc(sizeof(struct ListNode)); morehead->next = NULL; struct ListNode* cur = head; while (cur) { if (cur->val < x) { lesstail->next = cur; lesstail = lesstail->next; cur = cur->next; lesstail->next = NULL; } else { moretail->next = cur; moretail = moretail->next; cur = cur->next; moretail->next = NULL; } } lesstail->next = morehead->next; free(morehead); head = lesshead->next; free(lesshead); return head; }
