ઇଓ 欢迎来阅读子豪的博客（剑指offer刷题篇）

☾ ⋆有什么宝贵的意见或建议可以在留言区留言

ღღ欢迎 素质三连 点赞 关注 收藏

 ❣ฅ码云仓库：补集王子 (YZH_skr) - Gitee.com

链表分割_牛客题霸_牛客网 (nowcoder.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  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;    }};

记得 三连哦~