【Java版oj】链表分割

我不是女神ヾ 2024-04-01 09:03 65阅读 0赞

**目录**

一、原题再现

二、问题分析

三、完整代码

--------------------

> ## 一、原题再现 ##
> 
> [链表分割\_牛客题霸\_牛客网][Link 1]
> 
> 较难 通过率：22.11% 时间限制：3秒 空间限制：32M
> 
> ### 描述 ###
> 
> 现有一链表的头指针 ListNode\* **pHead**，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

> ## 二、问题分析 ##
> 
> 虽然这道题目认定的是较难，但只要仔细分析，找对了思路其实很容易解决。我们可以设想逻辑上存在两题链表：第一条链表保存所有小于x的全部结点，第二条链表保存所有大于x的全部结点。遍历原链表中的每个结点，利用尾插可以保证数据顺序不变。最后再将第一条链表和第二条链表合成一条链表。
> 
> 牛客题中有一个注意点，就是它链表的构造方法没有给定无参构造，所以我们在开辟新链表结点时要用有参构造 。即得赋值ListNode largeHead=new ListNode(-1);而不能ListNode largeHead=new ListNode();

> ## 三、完整代码 ##
> 
>     import java.util.*;
>     
>     /*
>     public class ListNode {
>         int val;
>         ListNode next = null;
>     
>         ListNode(int val) {
>             this.val = val;
>         }
>     }*/
>     public class Partition {
>        public ListNode partition(ListNode pHead, int x) {
>             // write code here
>             // 准备两个逻辑上的链表
>             // smalList：保存所有小于 x 的结点
>             ListNode smallHead=new ListNode(-1);//头结点
>             ListNode smallLast=smallHead;//尾结点
>             // largeList：保存所有大于等于 x 的结点
>             ListNode largeHead=new ListNode(-1);//头结点
>             ListNode largeLast=largeHead;//尾结点
>     
>             // 遍历链表中每个结点
>             ListNode cur=pHead;
>             while(cur!=null){
>                 ListNode curLast=cur.next;
>                 if(cur.val<x){
>                     //尾插
>                     cur.next=null;
>                     smallLast.next=cur;
>                     smallLast=cur;
>                 }else {
>                     cur.next=null;
>                     largeLast.next=cur;
>                     largeLast=cur;
>                 }
>                 cur=curLast;
>             }
>     
>             // 原链表的所有结点都被分到了两条链表中
>             smallLast.next=largeHead.next;//结合到一起，跳过smallHead和largeHead,这两个只是工具结点
>             return smallHead.next;
>         }
>     }
> 
> ![30999f0c2363496782aadd70b6ff6074.png][]

--------------------

![9153ef5d614d42c2a32968f612bb344d.png][]

[Link 1]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[30999f0c2363496782aadd70b6ff6074.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/80ca173d33e341b5af5a17c83851ee6a.png
[9153ef5d614d42c2a32968f612bb344d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ac9ce6ee7f254a7abb685adb10c8c3bf.png