当前位置: 首页 > article >正文

数据结构:(牛客)CM11 链表分割

描述

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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

#include <cfloat>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        typedef struct ListNode ListNode;
        //创建两个非空的链表:小链表,大链表
         ListNode *lessHead, *lessTail;
        lessHead=lessTail=( ListNode*)malloc(sizeof(ListNode));
        ListNode*greaterHead,*greaterTail;
        greaterHead=greaterTail=(ListNode*)malloc(sizeof( ListNode));
        //遍历链表,找到小于x的值尾插到小链表的尾结点,反之
        ListNode*pcur=pHead;
        while(pcur)
        {
            if(pcur->val<x)
            {
                lessTail->next=pcur;
                lessTail=lessTail->next;
            }
            else
            {
                greaterTail->next=pcur;
                greaterTail=greaterTail->next;
            }
            pcur=pcur->next;
        }
        //大小链表合并
        greaterTail->next=NULL;
        lessTail->next=greaterHead->next;
        ListNode*ret=lessHead->next;
        free(lessHead);
        free(greaterHead);
        lessHead=greaterHead=NULL;
        return ret;
    }
};


http://www.kler.cn/a/297180.html

相关文章:

  • 【Python基础学习】100个Python精选库
  • 萌新5:日历游戏(博弈论,递推找规律)
  • 【论文精读】 | 用于时间序列预测的通道对齐坚固的混合Transformer
  • vulhub spring 远程命令执行漏洞(CVE-2022-22963)
  • 【网络安全】分析JS文件实现账户接管
  • 数据结构:哈希表
  • java后端保存的本地图片通过ip+端口直接访问
  • LG AI研究开源EXAONE 3.0:一个7.8B双语语言模型,擅长英语和韩语,在实际应用和复杂推理中表现出色
  • vim常用快捷键
  • 数据库的操作:数据完整性约束是什么?
  • linux-基础知识3
  • Arduino IDE的安装
  • springcloud间通信的方式
  • 非标金属零件加工的质量与效率是如何体现的?
  • Figma如何给设计的UI套样机
  • RK3562 NPU供电要求
  • wordpress做后台的资讯类小程序源码
  • Anaconda Prompt 安装paddle2.6报错
  • 线程池实现服务端
  • Linux Runtime PM(运行时电源管理)框架API