Nowcoder .链表分割

哨兵位节点

链表分割

小于X 尾插到一个新链表
大于等于X 尾插到另一个链表
最后将两个链表链接起来

需要注意的细节：将第一个链表的尾与第二个链表的头相连接，再返回连接后的整个链表的头（哨兵位头节点的下一个）

我们可以把哨兵位的头节点当作真实头节点的前驱，它是一个不在答案范围内的节点，但它却可以有效的控制真实的链表。其里面的值可以是随机的，它的next初始指向NULL，如果有节点尾插，它的next就指向尾插的节点,而尾插的节点就是新连接的链表的真实的头。当最后连接完成时，我们想要返回这个链表，不能直接返回哨兵位的头节点 ，应该直接返回哨兵位的next，因为哨兵位的next才是有效的真实的头节点

使用哨兵位的头节点 可以极大可能的避免判断链表为NULL 的情况

class Partition {
public:ListNode* partition(ListNode* pHead, int x){struct ListNode* lesshead = (struct ListNode*)malloc(sizeof(struct ListNode));  //创建哨兵位头节点struct ListNode* greaterhead= (struct ListNode*)malloc(sizeof(struct ListNode));//创建哨兵位头节点 lesshead->next = NULL, greaterhead->next = NULL;struct ListNode* cur = pHead, * lesstail = lesshead, * greatertail = greaterhead;// 遍历原链表while (cur){// 如果小于x就尾插到lessheadif (cur->val < x) {lesstail->next = cur;lesstail=lesstail->next ;cur = cur->next;}else   //如果 >= x 就尾插到greaterhead {greatertail->next =cur ;greatertail=greatertail->next ;cur = cur->next;}}lesstail->next = greaterhead->next;	// 第一个的尾连接第二个的头// 将第二个的尾置为NULLgreatertail->next = NULL;  //防止成环 return lesshead->next; // 返回新链表的头// 分别释放创建的两个哨兵位头节点free(lesshead);free(greaterhead);}
};

需要注意一定要将两个链表链接起来一定要将新链表尾节点置NULL
我们假设 需要分割的链表是 1 5 2 7 3 4 X是 5
小于X 的链表是 1 2 3 4 大于等于X的链表是 5 7
最后将两个链表链接起来
如果此时没有将新链表的尾节点置NULL ,此时 7 的节点还保存了原链表 元素3 的地址就会形成环

如图所示

---

如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力！！！