链表分割

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目要求

链接：链表分割牛客题霸牛客网 (nowcoder.com)

描述

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

即：把结点的值小于x的放在左边，大于x的放在右边。相对顺序不可以改变

如果是不需要考虑相对顺序，左边存比x小的结点，右边存大于等于x的结点

思路：

• 创建一个新链表，定义头尾指针，方便头插和尾插
• 定义指针cur，用于遍历原链表
• 如果cur指向的值比x小：头插到新链表 ->更新头指针 否则尾插到新链表 ->更新尾指针

思路

• 创建两个带哨兵位的链表

• 一个用于存放值小于x的结点，记为lessHead，一个用于存放值大于等于x的结点，记为greaterHead

• 为了方便插入，两个链表分别定义头尾指针，用于标志头和尾。最初都指向哨兵位

• 定义一个指针cur用于遍历原来的链表

  • 如果cur指向的值小于x：尾插到lesstail的后面，然后更新lesstail的位置
  • 否则：尾插到greatertail的后面，然后更新greatertail的位置
  • 循环结束条件：把原链表的结点都遍历完成。即cur为空

• 由于值小于x的放在链表前面，所以最后：把lesstail->next链接greaterHead->next(greaterHead链表的第一个结点)

  注意点：

  1：lessHead和greaterHead为哨兵位，二者的next才是第一个结点

  2.要防止形成环(原链表的尾的前一个结点比x大，尾结点比x小，链接之后，会形成环)，所以要将greatertail->next置空

  

  3.要释放动态开辟的两个哨兵位，防止内存泄露。

  • 要先保存lessHead->next结点的位置记为newhead，不然释放之后就找不到了
  • 以newhead为头的链表就是比x小的在左边，比x大的在右边
  • 最后返回newhead即可

图解

链接时候：原链表的真实变化

例子：原链表为 5 -> 3 -> 6 -> 2 -> 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
        //链表为空，直接返回
        if(pHead == NULL)
        {
            return NULL;
        }
        //开辟两个链表 (使用哨兵位结点)
        struct ListNode*lessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode*greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        //为了方便尾插，再定义一个尾指针
        struct ListNode* lesstail = lessHead;
        struct ListNode* greatertail = greaterHead;
        
        //比x小的尾插到lessHead 大于等于x的尾插到greaterHead链表
        //cur用于遍历原链表
        struct ListNode* cur = pHead;
        while(cur)
        {
            //结点的值比x小，就链接到less的后面
            if(cur->val < x)
            {
                //链接cur
                lesstail ->next =cur;
                //更新less的尾结点
                lesstail = cur;
            }
            //结点的值大于等于x，就链接到greater的后面
            else
            {
                //链接cur
                greatertail -> next = cur;
                //更新greater的尾结点
                greatertail = cur;
            }
            //cur指向原链表的下一个结点
            cur = cur->next;
        }
        //链接两个链表
        //排成升序，所以是greater的第一个结点链接到less的尾
        lesstail->next = greaterHead -> next;//greater是哨兵位，greaterHead的next才是第一个结点
        //为了防止成环，要把greater的尾置空
        greatertail ->next = NULL;
        
        //防止内存泄露，要释放两个哨兵位结点
        //要先保存新链表的头
        struct ListNode* newhead = lessHead->next;//less的下一个结点才是头，less是哨兵位
        //释放两个哨兵位
        free(lessHead);
        free(greaterHead);
        return newhead;
    }
};

\