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

采用方法：

尾插法： 1.需要知道两个线段开始和结束 bs be as ae = null； 2.定义一个cur遍历原来的单链表 3.如果cur.data<x放到第一个线段，如果相反，就放到第二个线段 4.cur为空的时候就遍历完了

注意： 1.如果第一个段没有数据，就返回第二段的开头as 2.be和as进行拼接 bs.next = as;

代码语言：javascript复制

    //现有一链表的头指针 ListNode* pHead，给一定值x，
    // 编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public ListNode partition(int x){
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val < x){
                //第一次插入
                if (bs == null){
                    bs = cur;
                    be = bs;
                }else {
                    be.next = cur;
                    be = be.next;
                }
            }else {
                //第一次插入
                if (as == null){
                    as = cur;
                    ae = as;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //1.判断bs是否为空，如果为空，返回as
        if (bs == null){
            return as;
        }
        //2.如果bs不为空，需要进行拼接
        be.next = as;
        //3.如果ae不为空，则需要吧ae.next置为空
        if (ae != null){
            ae.next = null;
        }
        return bs;
    }

data null 遍历

0 人点赞