Leetcode 86) Partition List

27 Sep 2021 in Algorithms

My Answer

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null)return null;
        ListNode smaller=new ListNode();
        smaller.next= head;
        ListNode dummy = smaller;
        ListNode res =smaller;
        //dummy head set

        while(dummy.next!=null){
            if(dummy.next.val < x){
                if(dummy==smaller){
                    dummy=dummy.next;
                    smaller=smaller.next;
                    continue;
                }
                //store it separately
                ListNode target = dummy.next;
                //connect adjacent elements
                dummy.next= dummy.next.next;
                // attach stored element to smaller 
                ListNode next= smaller.next; 
                smaller.next= target; 
                target.next= next;
                smaller=smaller.next;

            }else{
                dummy=dummy.next;
            }
        }
        return res.next;
    }
}

Other Answer

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }    

        ListNode dummy = new ListNode(0);
        ListNode left = dummy;
        boolean firstLarge = false;
        ListNode flNode = null;
        ListNode walker = head, pre = null;
        while (walker != null) {
            if (walker.val < x) {
                left.next = walker;
                left = left.next;
                walker = walker.next;
                if (pre != null) {
                    pre.next = walker;    
                }
            } else {
                if (!firstLarge) {
                    firstLarge = true;
                    flNode = walker;
                }
                pre = walker;
                walker = walker.next;
            }
        }

        left.next = flNode;

        return dummy.next;
    }
}