开发者社区> IT辰柒_Java> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

【牛客刷题】每日一练—链表分割

简介: 【牛客刷题】每日一练—链表分割
+关注继续查看

✨hello,进来的小伙伴们,你们好耶!✨

🍖🍖系列专栏:【牛客刷题】

🍈🍈作者简介:一名双非本科大三在读的Java编程小白,启夜星辰,你我同行!

问题描述

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

解题思路:

1、我们可以定义四个节点,bs be 用于存储表示小于x的所有节点,as,ae表示用来存储大于等于x的节点,bs,as永远指向两段链表的头,be,ae指向两段链表的尾巴,这样就省去了每次需要找尾巴的麻烦,然后遍历链表把这些节点都存起来,最后通过be.next = as;将两段链表链接起来。

   import java.util.*;

     

   /*

   public class ListNode {

       int val;

       ListNode next = null;

       ListNode(int val) {

           this.val = val;

       }

   }*/

   public class Partition {

       public ListNode partition(ListNode head, int x) {

           //根据x,将链表中的数据划分成两部分

           //小于x的部分

           ListNode bs = null;

           ListNode be = null;

           //大于x的部分

           ListNode as = null;

           ListNode ae = null;

           while (head != null) {

               //判断当前head的val是哪一部分

               if (head.val < x) {

                   //判断是否是第一次插入

                   if (bs == null) {

                       bs = head;

                       be = head;

                   } else {

                       be.next = head;

                       be = be.next;

                   }

                   head = head.next;

               } else {

                   if (as == null) {

                       as = head;

                       ae = head;

                   } else {

                       ae.next = head;

                       ae = ae.next;

                   }

                   head = head.next;

               }

           }

           //链表数据全部大于x

           if (bs == null) {

               return as;

           }

           if (as != null) {

               ae.next = null;

           }

           be.next = as;

           return bs;

       }

   }


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【牛客刷题】每日一练—链表的回文结构
【牛客刷题】每日一练—链表的回文结构
0 0
【牛客刷题】每日一练——回文字符串
【牛客刷题】每日一练——回文字符串
0 0
【牛客刷题】每日一练——删除有序数组中的重复项
【牛客刷题】每日一练——删除有序数组中的重复项
0 0
【牛客刷题】每日一练—返回链表的中间节点
【牛客刷题】每日一练—返回链表的中间节点
0 0
【Java数据结构】经典链表OJ题——超详细做题笔记及心得(二)
【Java数据结构】经典链表OJ题——超详细做题笔记及心得(每行代码都有注释嗷)
0 0
【Java数据结构】经典链表OJ题——超详细做题笔记及心得(一)
【Java数据结构】经典链表OJ题——超详细做题笔记及心得(每行代码都有注释嗷)
0 0
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
【Java数据结构】经典链表OJ题——超详细做题笔记及心得
0 0
[leetcode/lintcode 题解]算法面试真题详解:外星人字典
[leetcode/lintcode 题解]算法面试真题详解:外星人字典
0 0
+关注
IT辰柒_Java
攀登者!
文章
问答
文章排行榜
最热
最新
相关电子书
更多
面试常考算法
立即下载
超全算法笔试 模拟题精解合集
立即下载
超全算法笔试-模拟题精解合集
立即下载