给单链表加一

问题描述

你可以假设这个整数除了 0 本身，没有任何前导的 0。
这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

示例:
输入: [1,2,3]
输出: [1,2,4]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/plus-one-linked-list

思路

从链表的最后一个节点开始，找到第一个不为9的位置

• 如果整个链表都为9，那么将原链表的节点的值都置为0，并在链表前加一个值为1的节点。
• 如果链表存在不为9的节点，该节点前边的节点值不变，该节点的值+1，该节点后边的值置为0。

题解

class Solution {
public:
    ListNode *plusOne(ListNode *head) {
        if (head == nullptr) return nullptr;
        ListNode *p = head;
        vector<int> vec;
        while (p != nullptr) {
            vec.push_back(p->val);
            p = p->next;
        }
        int location = -1;
        for (int i = vec.size() - 1; i >= 0; i--) {
            if (vec[i] != 9) {
                location = i;
                break;
            }
        }
        if (location == -1) {
            ListNode *tmphead = new ListNode(1);
            ListNode *tmp = head;
            while (tmp != nullptr) {
                tmp->val = 0;
                tmp = tmp->next;
            }
            tmphead->next = head;
            head = tmphead;
        } else {
            ListNode *tmp = head;
            int count = 0;
            while (count <location) {
                tmp = tmp->next;
                count++;
            }
            tmp->val = tmp->val + 1;
            tmp = tmp->next;
            while (tmp != nullptr) {
                tmp->val = 0;
                tmp = tmp->next;
            }
        }

        return head;
    }
};