前言

小伙伴们大家好啊！今天小编为大家带来一篇牛客网上，有关链表分隔的一道相对比较复杂的题目。虽然大家可能对单链表已经见怪不怪了，因为我们确实接触到了很多有关单链表的操作，比如单链表的合并，查找单链表某个指定节点，以及删除单链表指定位置的元素。

情景化分析

有时候在特定的场合我们有以下做法：

这就相当于我们排队，大家都是随便排的。

但是这时候管理员要求小朋友排到前面，此时，小朋友们开始移动，但是大人原先站相对位置时不变的，因为大人是不要求移动的，只能被动的移动，所以大人之间的相对位置也是不变的。

也就是说，只有前面小孩子排满了，站不下了，大人全部一起往后移动。同时，小朋友之间的相对位置也是不能变的。（小朋友相当于小于指定数的节点，大人相当于大于指定数的节点）

那么这样排完对之后，前面全部是小孩子，但是大小层析不齐，因为我们没有要求还需要按照身高再排队。后面的大人也是。但是这已经完成了我们的“链表分隔”。

tips：这篇文章小编最主要想要提出的一个问题是，单链表有无头指针对于单链表的影响。

如果那个小伙伴对于单链表头指针有无还有一些问题的话，快速食完，你会感谢我的哦！我们废话不多说，进入正文。

一，案例题目分析

1.1题目要求

如下图所示，这是一篇牛客网上比较难的一道题。但是在小编看来，如果对于链表的尾插小伙伴们掌握不错的话，属于简单题型了哦！

1.2题目解析

题目中要求，我们需要将一个链表中的所有小于给定值 x 的节点全部移动到其他节点之前，但是要求是不能打乱原先链表的顺序。也就是一些元素的相对位置时不能变的。也就是开头我们情景化分析的排队问题。

二，思路分析

1.2 第一步思路

那么我们知道，其实对于该链表而言，因为后面我们不想在插入的时候用尾插的方式，那么如果这样的话，我们是需要用一个不存储数据的头节点的，这样就假设我们有头节点了。然后在插入新链表的时候，就不需要考虑是否是头节点的插入了。

这样做虽然最后我们需要将 malloc 开辟的空间释放，但是与头插而言，释放空间需要的思路和步骤太简单了。所以这里我们用malloc开辟两个新节点。而这两个新链表分别有两个指针，用来表两个链表的头和尾。

1.2之后步骤

通过以上步骤，我们新建了两个空链表，接下来我们就需要进行比较步骤了。

第一步：从原链表的头节点开始，依次与给定值进行比较，如果该节点的值小于给定值，那么将尾插到 lessHead 链表，反之则尾插到 greaterHead 链表。

第二步：直到原链表的所有元素全部移动完之后，最后我们需要将连个链表链接在一起，显而易见的就是需要将 lessHead 的尾指针 lessTail 的 next 链接到 greaterHead 链表的next 位置，最后一定不能忘记的还有最后的尾指针 greaterTail 需要置空。

三，源码分享

那么经过以上分析之后，我们发现，这个题变得没有那么复杂了。

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode*cur,*lessTail,*greaterTail,*lessHead,*greaterHead;lessTail=lessHead=(struct ListNode*)malloc(sizeof(struct ListNode));lessTail->next=lessHead->next=NULL;greaterTail=greaterHead=(struct ListNode*)malloc(sizeof(struct ListNode));greaterTail->next=greaterHead->next=NULL;cur=pHead;while(cur){if(cur->val < x){lessTail->next=cur;//lessTail=cur;lessTail=lessTail->next;}else{greaterTail->next=cur;//greaterTail=cur;greaterTail=greaterTail->next;}cur=cur->next;}lessTail->next=greaterHead->next;greaterTail->next=NULL;struct ListNode*newnode=lessHead->next;free(lessHead);free(greaterHead);return newnode;}
};

当然，既然有了思路，那么代码实现是比较简单的，但是这里小编想提醒各位小伙伴们。有没有头指针是很重要的，有了之后很多东西会变得不那么冗余，但是同时一定不能忘记释放哦！

以及有了头指针之后，其实在返回的时候，我们并不会连带头指针，因为头指针并没有存储数据。所以这里我们是将头指针的 next 返回了。

好的，那么本文到此就结束啦。如有小伙伴有问题，可随时提问哦！

“小朋友大人排队”问题（十分钟带你玩转 牛客网 CM11 链表分隔）

前言