Java Solution using DFS with O(n) Time Complexity


  • 0
    Y
    public class Solution {
        private int c = 0;
        public ListNode plusOne(ListNode head) {
            ListNode ans = new ListNode(1);
            if(head == null)
                return ans;
            dfs(head);
            if(c == 1)
                ans.next = head;
            else
                ans = head;
            return ans;
        }
        
        public void dfs(ListNode p){
            if(p.next == null)
                ++ p.val;
            else{
                dfs(p.next);
                p.val += c;
            }
            c = p.val>=10?1:0;
            p.val = p.val>=10?p.val%10:p.val;
        }
    }

Log in to reply
 

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