Java in place solution O(n)


  • 0
    K
    public class Solution {
        public ListNode partition(ListNode head, int x) {
            if(head == null || head.next == null) return head;
            ListNode last = head;
            ListNode dummy = new ListNode(Integer.MIN_VALUE);
            dummy.next = head;
            ListNode prev = dummy;
            int length = 1;
            //get the last node and length of the list
            while(last.next != null) {
                last = last.next;
                ++length;
            }
            int moves = 0, ptr = 1;
            //add bigger nodes to end of the list
            while(head.next != null && length-moves >= ptr) {
                if(head.val >= x) {
                    prev.next = head.next;
                    last.next = head;
                    head.next = null;
                    last = last.next;
                    head = prev.next;
                    ++moves;
                } else {
                    prev = head;
                    head = head.next;
                    ++ptr;
                }
            }
            return dummy.next;
            
            
        }
    }
    

Log in to reply
 

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