???欢迎来阅读子豪的博客（剑指offer刷题篇）
? ?有什么宝贵的意见或建议可以在留言区留言
??欢迎?素质三连?点赞 关注 收藏
???码云仓库：补集王子 (YZH_skr) - Gitee.com
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
目录
?难点
相对顺序不变
思路
运用带哨兵位的头结点（尾插的题尽量都用哨兵位）
定义两个链表
尾插
?
连接+释放
?
?
考虑极端场景
原来链表最后一个比x大
就会把大的那个写到新链表的最后一个去 但是这个的next是指向前面的 就会出现一个环
??
需要把最后一个置空
整体代码
class Partition {
public:
ListNode* partition(ListNode* pHead, int x)
{
ListNode *greatertail , *greaterhead, *lesshead, *lesstail;
greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode)); //哨兵位
lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode)); //哨兵位
greaterhead -> next = NULL;
lesshead ->next = NULL;
struct ListNode* cur = pHead; // 工具指针
while(cur)
{
if(cur -> val < x)
{
lesstail -> next = cur;
lesstail = lesstail->next;
}
else
{
greatertail -> next = cur;
greatertail = greatertail->next;
}
cur = cur->next;
}
lesstail->next = greaterhead->next;
greatertail->next = NULL;
struct ListNode* head = lesshead->next;
free(greaterhead);
free(lesshead);
return head;
}
};记得 三连哦~
