A unique Java Solution; O(n); best space utilization


  • 0
    A

    Used just one Linked list instead of two; which is the case in other solutions

        public ListNode partition(ListNode head, int x) {
            if(head == null || head.next == null){
                return head;
            }
            ListNode Big = new ListNode(0);
            ListNode BigCurrent = Big;
            ListNode iterator = new ListNode(0);
            iterator.next = head;
            ListNode returnHead = iterator;
            while(iterator.next != null){
                if(iterator.next.val < x){
                    iterator = iterator.next;
                }else{
                    BigCurrent.next = new ListNode(iterator.next.val);
                    BigCurrent = BigCurrent.next;
                    iterator.next = iterator.next.next;
                }
            }
            iterator.next = Big.next;
            return returnHead.next;
        }
    }

Log in to reply
 

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