欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java leetcode&NC 链表分割

程序员文章站 2022-07-06 15:26:58
题目描述编写程序以 x 为基准分割链表,使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x,x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可,其不需要被置于左右两部分之间。例如:输入: head = 3->5->8->5->10->2->1, x = 5输出: 3->1->2->10->5->5->8来源:力扣(LeetCode)链接:NC链表分割   Le...

题目描述

编写程序以 x 为基准分割链表,使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x,x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可,其不需要被置于左右两部分之间。

例如:
输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

来源:力扣(LeetCode)
链接:NC链表分割
   LeetCode分割链表

实现代码

public ListNode partition(ListNode pHead, int x) {
        
        if(pHead == null){
            return null;
        }
        ListNode cur = pHead;
        ListNode bs = new ListNode(-1);
        ListNode be = bs;
        ListNode as = new ListNode(-1);
        ListNode ae = as;
        
        while(cur != null){
            if(cur.val < x){
                
                    be.next = cur;
                    be = be.next;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            cur = cur.next;
        }
        //判断bs指向结点的指针域是否为空,为空则表明前半段没有结点
        if(bs.next == null){
            return as.next;
        }
        //前半段最后一个结点的指针域放置后半段链表的头指针
        be.next = as.next;
        //as指向结点的指针域象不为空表明链表后半段有结点,一定要将链表最后结点指针域置空
        if(as.next != null){
            ae.next = null;
        }
        //返回新的链表头指针
        return bs.next;
     }

牛客&力扣运行结果:
Java leetcode&NC 链表分割
Java leetcode&NC 链表分割

本文地址:https://blog.csdn.net/weixin_44874269/article/details/112529574