JAVA O(1) space solution


  • 0
    Q

    The in-place or O(1) space idea is to go though the list and if the value of the node is greater or equal than x, put the node to the end of the linked list.

            if(head == null || head.next == null){
                return head;
            }
    
            int count = 1;
            ListNode tail = head;
            while(tail.next != null){
                tail = tail.next;
                count++;
            }
    
            ListNode newHead = new ListNode(0);
            newHead.next = head;
            ListNode cur = head;
            ListNode next;
            ListNode pre = newHead;
    
            while(count > 0)
            {
                next = cur.next;
                if(cur.val < x){
                    cur = cur.next;
                    pre = pre.next;
                }
                // Put cur to tail
                else{
                    // Corner case !!!
                    if(cur == tail){
                        count--;
                        continue;
                    }
                    pre.next = next;
                    cur.next = null;
                    tail.next = cur;
                    tail = tail.next;
                    cur = next;
                }
                count--;
            }
    
            return newHead.next;
    

Log in to reply
 

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