算法通关村第二关——单链表加1的问题解析

迈不过友情╰ 2024-03-22 22:18 43阅读 0赞

### 题目类型 ###

> 链表反转

### 题目描述 ###

> 用一个非空单链表来表示一个非负整数，然后将这个整数加一。你可以假设这个整数除了0本身，没有任何前导的0.
> 
> 这个整数的各个数位按照 高位在链表头部，低位在链表尾部 的顺序排列

#### 示例 ####

> 输入：\[1,2,3\]
> 
> 输出：\[1,2,4\]

#### 思路分析 ####

> 1. 计算是从低位开始的，而链表是从高位开始的，所以要计算，就必须将链表反转过来，反转操作可以使用链表反转来实现，也可以使用栈来实现。

> 2. 基于栈的实现思路：先把题目给的链表压入栈中，然后从栈中弹出栈顶数字digit，加的时候再考虑下进位的情况，加完之后根据是否大于0决定 下一次是否要进位

#### 代码实现 （栈） ####

/**
         * 题目：
         * 用一个非空单链表来表示一个非负整数，然后将这个整数加一。你可以假设这个整数除了0本身，没有任何前导的0.
         * 这个整数的各个位数按照  高位在链表头部、低位在链表尾部  的顺序 排列
         * @param head 链表头节点
         * @return  加一操作后的链表头节点
         */
        public Node singleListAdd1(Node head){
            Stack<Integer> stack = new Stack<>();
            while (head != null){
                stack.push(head.data);
                head = head.next;
            }
            // 定义数据
            // carry 用于存储进位标识。如果carry为0，表示没有进位；如果carry为其他数，则表示有进位
            int carry = 0;
            // addNum 表示加1 操作的变量。如果是最低位，进行加1，然后将其置为0
            int addNum = 1;
            // 虚拟节点
            Node dummyNode = new Node(0);
    
            while (!stack.empty() || carry >0){
                // digit 翻译为数字，表示从栈中取出来的数据（从低位（个位）  ===》 到高位（十位、百位））
                int digit = stack.empty() ? 0 : stack.pop();
                // sum 翻译为和，表示  一个位的值+ addNum（如果该位为个位，则表示第一次循环，可以加1，在结束本次循环后，被置为0）+ 进位标识（如果有进位，也只是进1)）
                int sum = digit + addNum + carry;
                // 先判断sum 是否能进位，如果能进位（值大于10），将carry置为1；不能进位（值小于10），置为0
                carry = sum >= 10 ? 1 : 0;
                // 先判断sum的值是否大于10，如果大于10，说明之前有进位，此时就需要将sum的值减10；如果小于10，标识刚刚没有进位，返回原来的数
                sum = sum >= 10 ? sum - 10 : sum;
                // 将 该位最后算得的值作为当前节点
                Node cur = new Node(sum);
                cur.next = dummyNode.next;
                dummyNode.next = cur;
                // addNum只为最低位（个位）进行加1操作，当进行完加1操作后，需要将其置为0
                addNum = 0;
            }
            return dummyNode.next;
        }

> 基于反转链表实现：因为在开始前和结束后都需要反转链表，因此可以将反转链表提取成一个方法，并返回反转后的头节点，然后再做+1操作

#### 代码实现（反转链表） ####

public Node singleListAdd1ByReverseList(Node head){
            head = reverseList(head);
            Node dummyNode = new Node(0,head);
            Node cur = dummyNode;
            int carry = 0;
            int addNum = 1;
            while (head != null){
                int val = carry;
                val += head.data +addNum;
                head = head.next;
                int ans = val % 10;
                carry = val / 10;
                cur.next = new Node(ans);
                addNum = 0;
                cur =cur.next;
            }
            if (carry > 0){
                cur.next = new Node(carry);
            }
            return reverseList(dummyNode.next);
        }
    
        private Node reverseList(Node head){
            Node pre = null;
            Node cur = head;
            Node next;
            while (cur != null){
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }