[LeetCode 369] Plus One Linked List (Medium)

Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

• You may assume the integer do not contain any leading zero, except the number 0 itself.
• The digits are stored such that the most significant digit is at the head of the list.

Example :

Input: [1,2,3]
Output: [1,2,4]

Solution

• 与 LeetCode 445 Add Two Numbers II 类似，首先翻转链表，然后做Plus One操作；完成后再次翻转链表。
• 此代码中，用count表示是否是第一位需要加一，count初始为0，如果已经进行了第一位的加一操作，count ++，那么后面则不再进行加一。
• 也可以创建一个只有一个节点（value为1）的链表，然后用 LeetCode 445 的方法即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        if (head == null)
        {
            return head;
        }
        
        head = reverse (head);
        
        ListNode dummy = new ListNode (0);
        ListNode node = dummy;
        
        int carry = 0;
        int count = 0;
        
        while (head != null)
        {
            int sum = head.val + carry + (count == 0 ? 1 : 0);
            count ++;
            int digit = sum % 10;
            carry     = sum / 10;
            
            ListNode temp = new ListNode (digit);
            node.next = temp;
            node = temp;
            
            head = head.next;
        }
        
        if (carry > 0) {
            ListNode temp = new ListNode (carry);
            node.next = temp;
        }
                
        return reverse (dummy.next);
    }
    
    public ListNode reverse (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode prev = null;
        
        while (head != null)
        {
            ListNode next = head.next;
            head.next = prev;
            
            prev = head;
            head = next;
        }
        
        return prev;
    }
}