Two Pointers with fakeHead -- JAVA Solution


  • 0
    X
     public class Solution {
      public ListNode plusOne(ListNode head) {
        ListNode fake = new ListNode(0); // put fake head in the beginning
        fake.next = head;
        
        boolean fakeHead = false; // fake head will be new header or not.
        
        ListNode p = fake;
        ListNode q = head;
        while(q!=null){
            if(q.val != 9) p = q; //find the first non-9 to be p
            q = q.next;
        }
        
        if(p == fake) fakeHead = true; 
        //find p is still in the fake position, then fake will be the new head
        
        while(p!=null){
            if(p.val != 9) 
                p.val++; //change the first non-9(if fakeHead == true, this is fakeHead's 0) to be ++ number
            else p.val = 0; // change the rest 9 to 0.
            p = p.next;
        }
        
        if(fakeHead) return fake; // fakeHead is new head
        else return head; // head is still head
    }
    

    }

    Time complexity is O(N), space is O(1)


  • 0
    D

    Very neat solution!


Log in to reply
 

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