Plus One Linked List (0369/Medium)

链表加一运算

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

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

先把链表翻转一下，然后现在就是链尾是高位了，我们进行加1处理运算结束后，再把链表翻转回来即可

public ListNode reverseList(ListNode head) {
        ListNode first = head;
        ListNode reverseHead = null; //建立一个新的节点用来存放结果
        while (first != null) { //遍历输入链表，开始处理每一个节点
            ListNode second = first.next; //先处理第一个节点first，所以需要一个指针来存储first的后继
            first.next = reverseHead; //将first放到新链表头节点的头部
            reverseHead = first; //移动新链表的头指针，让它始终指向新链表头部
            first = second; //继续处理原链表的节点，即之前指针存放的后继，循环往复
        }
        return reverseHead;
}

public ListNode plusOne(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode tail = reverseList(head);
        ListNode cur = tail;
        ListNode pre = cur;
        int carry = 1;

        while(cur != null){
            pre = cur;
            int sum = cur.val + carry;
            cur.val = sum%10;
            carry = sum/10;
            if(carry == 0){
                break;
            }
            cur = cur.next;
        }
        if(carry == 1){
            pre.next = new ListNode(1);
        }
        return reverseList(tail);
    }