Golang O(n) solution, using 1 pointer


  • 0

    If there is consecutive 9 to the tail, we set a pointer just one node before 9 starts.
    e.g.) If a list is like 1, 2, 9, 9, 9, we set a pointer to 2.

    Also we need a special handling when all values are 9 (= head is 9 and need to sum up).

    func plusOne(head *ListNode) *ListNode {
        cur := head
        isHeadNine := cur.Val == 9
        var mark *ListNode
        
        for cur.Next != nil {
            if cur.Next.Val == 9 && mark == nil {
                mark = cur // first node before 9 starts only should be marked
            } else if cur.Next.Val != 9 {
                mark = nil 
            }
            cur = cur.Next
        }
        
        cur.Val += 1
        if cur.Val <= 9 {
            return head // no need to consider carry over
        }
        
        cur.Val = 0
        for mark != nil && mark != cur {
            mark.Val = (mark.Val + 1) % 10
            mark = mark.Next
        }
    
        if isHeadNine {
            return &ListNode{Val:1, Next: head}
        }
        return head
    }
    

Log in to reply
 

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