Java Solution with 1ms, easy to understand with some comments.


  • 1
    public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null||head.next==null) return head;
        ListNode dummy=new ListNode(Integer.MIN_VALUE);
        dummy.next=head;
        boolean hasLarge=false;  // to label if there exsits a large number
        ListNode small=null,p=dummy,pre=null;
        while(p!=null){
            if(p.val<x){
                if(small==null||!hasLarge){
                    small=p;
                    pre=p;
                    p=p.next;
                }
                else {
                    ListNode pnext=p.next;
                    ListNode smallnext=small.next;
                    small.next=p;
                    p.next=smallnext;
                    pre.next=pnext;
                    small=p;
                    p=pnext;
                }
                
            }
            else{
                hasLarge=true;
                pre=p;
                p=p.next;
            }
           
        }
        return dummy.next;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.