牛客CM11 - 链表分割【环形链表雏形】

一、题目描述

描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

• 是的，这题的题目描述总共就这么些，将就着看吧。。。
• 刷了这么多力扣，转牛客刷刷链表的题，但是这给到题目确实有些【简略】了，你可进网站看看，我有没有骗你

原题传送门

二、思路分析

好，看完题目的描述，我们来分析一下去求解这道题目

• 好，虽然本题的题目描述有些简略，而且连示例都没有，但这正好是锻炼我们的最佳时机，因为有些公司笔试给你的OJ题目网站也是有可能没有测试案例，这个时候你只能自己去猜测，然后慢慢画图构思，再将自己的思路转化为代码，接下去我们一起来分析一下本题如何求解

• 首先对于本题的题目描述我们先来理解一下，就是对于给定的一个链表一个一个定值，现在要将比这个【x】要小的数均放在其余结点之前，而且还要保持其相对顺序不变，有些同学可能没有理解题目意思，我们来画个图分析一下

• 简单地画了张图，题目的意思大概我下面所描述的这样👇

---

• 但是很多同学一定在看了我这张图之后还是没有一个很好的思路，确实，这道题分析起来比较复杂，若是你没有一个巧妙的思路，就很难去得心应手地写出代码，因此需要去想到一个思路，但是光这么做交换真的可以吗，这其实就是你的思维太局限了，为什么题目不给出示例，其实我想也是有它的道理的，放置禁锢了你的思维，上面这个案例只是我随机想的，还有很多的案例，每个案例可能需要使用的方法并不同，因此我们需要进行一个分类讨论
• 但是在这之前我要先给出你一个整体的题目思路，我的思路是这样的
• 因为给出的【x】是一个定值，所以可以将这个分割后的链表分为两部分，一部分是【< 5】的，一部分是【>= 5】的，分别将这两部分也定义为链表结构，并且为他们设置头结点，也就是带头的单链表，因为我试了不带头的链表在写起程序来会比较复杂，因为第一次尾插都需要判断头是否为空，所以我后来选择使用带头的单链表进行操作。对于原先的链表，需要定义一个【cur】指针去一一遍历，找到比5小的，就链接在第一个链表后面，找到大于等于5的，就链接在第二个链表后面。

• 然后当结点全部链接完成后，将【lessTail】的next指向【greaterHead】的下一个结点，也就是第二个链表的首结点，最后在保存一个第一个链表的首结点返回，得到的就是按照定值分割后的链表

---

三、代码详解【保姆级教学】

• 好，有了这个思路，接下去我们来写代码试试看
• 首先要开辟四个链表指针，这个没办法

ListNode* lessHead, *lessTail, * greaterHead, *greaterTail;
1

• 然后分别对两个链表的头进行的一个动态开辟，申请好一块空间

lessHead = lessTail = (ListNode *)malloc(sizeof(ListNode));
greaterHead = greaterTail = (ListNode *)malloc(sizeof(ListNode));
1
2

• 接着既然是尾插，就要将尾指针的next域置为NULL

lessTail->next = greaterTail->next = NULL;
1

• 遍历原先链表的结点指针一定也不能少

ListNode* cur = pHead;
1

• 接下去就是这段链表分割与重新链接的过程了，这段逻辑要放到一个循环里，知道原先的链表遍历结束为止，代码很简单，这段逻辑对你来说应该不难

while(cur)
{
    if(cur->val < x){
        lessTail->next = cur;
        lessTail = lessTail->next;
    }else{
        greaterTail->next = cur;
        greaterTail = greaterTail->next;
    }
    cur = cur->next;
}
1
2
3
4
5
6
7
8
9
10
11

• 接下来就是在链接完后将两个链表做一个拼接，也非常直观

lessTail->next = greaterHead->next;
1

• 最后，我们去复用一下题目给出的原链表头结点，是其为【lessHead->next】，这样就可以获取到新链表的头，最后的话不要忘了将动态开辟出来的两个头结点指针进行一个释放，养成良好习惯，在牛客里不会出问题，但是呢对于我们日常的开发来说，若是没有在申请内存后及时地释放掉，就会造成【内存泄漏】

pHead = lessHead->next;
free(lessHead);
free(greaterHead);
return pHead;
1
2
3
4

• 但是从测试用例可以看出，牛客这里是报出了一个叫做【内存超限】的错误，这个的话其实和【超时】比较类似，你可能会想是我们在上面开辟了太多遍历又去申请内存导致的，但是事实却不是这样，想知道的就继续看下去吧❤️

四、环形链表的疑难解惑

• 上一小节我们说到了这个【内存超限】的原因，其实并不是因为我们申请的指针变量过多，而是程序的运行导致所占的内存过多，为什么我这样说呢，我通过讲解的这组测试案例运行一下你就知道了
• 从图中我们可以看到，当我去测试运行一下这组例子的时候，实际的输出结果是很多的数字，但是我们想要的结果是【2 3 4 2 6 7】这6个数字，那其实就可以明白为什么会【内存超限】了，这么多的内容不超才怪呢，就算是【牛】也把持不住呀，是吧🐮

• 那我们就要去分析为什么会产生这种情况？首先就是要去想一下有没有什么特殊情况，总结情况我做了一个罗列，大概就是下面五种，我们刚才进行的判断是后面两种，但是对于有大有小这一种其实还要细分为比较特殊的两种

• 首先来看一下这个测试案例，可以看到原先链表的最后一个结点【6】是大于5的，因此放到第二个链表处，而给出的链表的尾结点一定是指向NULL，是一个正常的链表，因此第二个链表的最后一个6也是指向NULL

• 这里要给大家说一点的是这两句代码，这也是我刚才忽略的内部循环逻辑，但是现在想起来还是要说一下，对于将当前结点链接到新的链表之后，那么这个【cue->next】会发生变化吗，答案是：不会的

lessTail->next = cur;
1

greaterTail->next = cur;
1

• 所以上面这样图你其实应该理解成这样，虽然你将这个6链接到第二个链表之后了，但是它的【next】指针域还是指向这个【NULL】的，你并没有对这个指针域做修改

---

• 然后我们再来看一个一开始我们讲解的案例
• 可以看到，对于原先链表的最后一个结点为2，最后将其链接到第一个链表时，修改了它的【next域】，原本2的next应该是指向NULL，现在修改了一下其指向，便指向第二个链表的开头6，但是第二个链表的尾结点7，它的【next域】又是指向谁的呢？没错，它还是指向原先链表中的4，在新链表中也就成了这个样子
• 这回你应该明白上面在跑这个测试用例的时候为什么会出现很多一模一样重复的数字了吧，其实就是因为新的链表尾还是指向原先的结点，使得这个链表的一些结点形成了一个环，于是在后半部分打印的时候，就变成了一个死循环，从而导致了内存的超限

• 这么分析下来，相信你对这个代码改如何修改应该很清楚了吧，没错，就是将第二个链表的尾指针【greaterTial->next = NULL】，这样就可以应对特殊的测试用例了，我们来提交一下试试

• 过了！！！不得不说，这个声音虽然很重，但是挺多了还是很悦耳的🐶

五、整体代码展示

展示一下整体的代码，可以看到，我写了一些注释，而且我的思路是很清晰的，对于做题，就是需要将复杂的问题进行一步步地拆分，将一层层的逻辑理清了，这样才能分析到问题的本质！！！

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        //1.初始化定义结构体指针
        ListNode* lessHead, *lessTail, * greaterHead, *greaterTail;
        //2.为两个链表头分别申请空间
        lessHead = lessTail = (ListNode *)malloc(sizeof(ListNode));
        greaterHead = greaterTail = (ListNode *)malloc(sizeof(ListNode));
        //3.初始化链表尾指针指向
        lessTail->next = greaterTail->next = NULL;
		
        ListNode* cur = pHead;		//遍历原链表的结点指针
        //4.内部遍历分割重组逻辑
        while(cur)
        {
            if(cur->val < x){
                lessTail->next = cur;
                lessTail = lessTail->next;		//链接到另一个链表并不会修改其next指向
            }else{
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        //5.链接两个链表
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;		//记住特殊情况，将尾结点指针置为NULL
		//6.获取新链表的头
        pHead = lessHead->next;
        free(lessHead);
        free(greaterHead);		//及时释放申请的内存，放置内存泄漏
        return pHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

六、总结与提炼

• 最后我们来总结一下本文所介绍的内容，本文讲解的是一道牛客网中的题目：【链表分割】，对于本题与大多数题目不同的一点首先是做起来很吃力，因为没有示例，而且在报出运行错误的时候会有一大堆的数字，若是太急便很难去静下心来仔细分析。
• 而且本题的难点在于对于特殊情况的指针，需要做一个特殊的修改，否则就会像我们看到的那样，造成【内存超限】，这个报错在力扣上是没有的，对于牛客来说，它的整体完善度虽然没有力扣那么高，题库和测试用例也没有力扣来的全，但是对于本题，我觉得很好地提升了分析算法题的能力。我们不能一直呆在温室里，也要有阳光的照射才能真正成长

以上就是本文所要描述的所有内容，感谢您对本文的观看，如有疑问请于评论区留言或者私信我都可以🍀