对链表依据指定值进行分割（java实现）

朱雀 2024-03-17 10:46 2阅读 0赞

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

实例：  
![在这里插入图片描述][0dc596148848478eaa7661d95b17ceed.png]原题OJ链接：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

解答

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) {
        
            ListNode cur = pHead;
            ListNode as = null;
            ListNode ae = null;
            ListNode bs = null;
            ListNode be = null;
            while(cur != null){
        
                if(cur.val < x){
        
                    if(ae == null){
        
                        as = cur;
                        ae = cur;
                        cur = cur.next;
                    }
                    else{
        
                        ae.next = cur;
                        ae = ae.next;
                        cur = cur.next;
                    }
                }
                else{
        
                    if(be == null){
        
                        bs = cur;
                        be = cur;
                        cur = cur.next;
                    }
                    else{
        
                        be.next = cur;
                        be = be.next;
                        cur = cur.next;
                    }
                }
            }
            if(as == null){
        
                return bs;
            }
            ae.next = bs;
            if(bs != null){
        
                be.next = null;
            }
            return as;
        }
    }

[0dc596148848478eaa7661d95b17ceed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/565e14c201914b4fa7acfeb9c2718f7c.png