96. 链表划分链表拆分

给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。 你应该保留两部分内链表节点原有的相对顺序。 样例 给定链表 1->4->3->2->5->2->null,并且 x=3 返回 1->2->2->4->3->5->null


链表拆分

根据与x的大小不同分别插入到两个链表里,然后把两个链表合并。简单的写法是新建链表节点,效率稍低,直接操作指针也可,注意细心别出错即可。 这种方法的一个缺点是:当x出现多次而且时会出错,这道题应该是假设x只出现一次。当x出现多次时,如果要求这些x在链表中是相连的话,那就用三个链表来做,把相等的时候放入另外一个链表,然后处理完之后再链接起来。

 ListNode * partition(ListNode * head, int x) {
        
        if(head==NULL)    //如果是空链表,返回空
            return NULL;
            
        ListNode *small=new ListNode(0);         //小列表的假表头
        //这个假表头应该是实体,因为操作的是它的next,如果本身就是空的,那么操作next就会出错。
        ListNode *small_back;   //最后一节点
        ListNode *big=new ListNode(0);           //大列表的假表头
        ListNode *big_back;     //最后一个节点
        
        ListNode *tmp=NULL;
        
        while(head)         
        {
            tmp=head;
            
            head=head->next;   //HEAD被tmp接管,head后移
            
            tmp->next=NULL;
            
            if(tmp->val<x)
            {
                if(!small->next)  //还是空的
                {
                    small->next=tmp;   //第一个接上来
                    small_back=small->next;   //后移
                }
                else
                {
                    small_back->next=tmp;
                    small_back=small_back->next;

                }
            }
            else
            {
                if(!big->next)
                {
                    big->next=tmp;
                    big_back=big->next;
                }
                else
                {
                    big_back->next=tmp;
                    big_back=big_back->next;

                }
            }
            
        }
        if(!small->next)   return big->next;    
//这里的判断一定要写next,新建假表头一切以假表头为准,一开始忘记写next怎么也通不过,气死!
        if(!big->next)    return small->next;
        small_back->next=big->next;
        return small->next;
        
            // write your code here
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java技术栈

Java父类强制转换子类原则

最近,微信群友在讨论子类父类的转换问题,其实不难,给大家用实例来说明一下就很明了了。 我们知道Java中子类转换成父类是没有任何问题的,那父类可以转换成子类吗?...

46580
来自专栏指尖下的Android

二进制的运算

在计算机中存储字节是定长的,即我们8、16、32位等等,6的二进制位为110,但如果在8位计算机中是00000110,高位补零

26430
来自专栏书山有路勤为径

k个排序链表的合并

LeetCode 23. Merge k Sorted Lists 已知k个已排序链表头节点指针,将这k个链表合并,合并后仍为有序的,返 回合并后的头节点。

11630
来自专栏Android干货

Python基础知识点

14440
来自专栏和蔼的张星的图像处理专栏

451. 两两交换链表中的节点链表处理

给一个链表,两两交换其中的节点,然后返回交换后的链表。 样例 给出 1->2->3->4, 你应该返回的链表是 2->1->4->3。 你的算法只能使用常...

21230
来自专栏C/C++基础

合并两个有序链表

已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序。结果链表要包含head1和head2的所有节点,即使节点值相同。

20320
来自专栏程序生活

Leetcode-Easy21. Merge Two Sorted ListsDefinition for singly-linked list.class ListNode:def init(sel

21. Merge Two Sorted Lists 描述: 将两个有序链表进行合并,合并之后的链表也是有序链表 ? 思路: 递归 代码 ...

27930
来自专栏Play & Scala 技术分享

Scala 谜题 - 有趣的类型转换

34870
来自专栏Albert陈凯

Scala集合练习题

//创建一个List val list0 = List(1,7,9,8,0,3,5,4,6,2) //将list0中每个元素乘以10后生...

49490
来自专栏大数据学习笔记

Java程序设计(Java9版):第2章 数据类型与运算符(Data types and Operators)

第2章 数据类型与运算符(Data types and Operators) I think everybody in this country should ...

28850

扫码关注云+社区

领取腾讯云代金券