力扣2816题：链表数字翻倍 - 栈处理与进位算法详解

内容简介

本文详细解析了力扣2816题"链表数字翻倍"的高效解法。通过使用栈结构处理链表数字，实现了数字翻倍和进位处理的完整过程。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握链表数字处理的实用技巧。

算法思路

1‌.栈存储‌：使用栈结构存储链表中的数字

‌2.数字处理‌：从低位到高位处理数字翻倍和进位

‌3.结果构建‌：将处理后的数字重新存入链表

‌4.进位处理‌：处理最高位可能的进位情况

代码实现（带详细注释）

class Solution {
public:
    ListNode* doubleIt(ListNode* head) {
        int carry = 0;          // 进位标志
        stack<int> originalStack, resultStack; // 原始数字栈和结果栈
        ListNode* originalHead = head; // 保存原始链表头
        ListNode* tailNode = nullptr;  // 记录链表尾节点
        
        // 第一次遍历：将链表数字压入栈并找到尾节点
        while(head) {
            originalStack.push(head->val);
            if(head->next == nullptr) {
                tailNode = head; // 记录尾节点
            }
            head = head->next;
        }

        int currentDigit;
        // 第二次遍历：处理数字翻倍和进位
        while(!originalStack.empty()) {
            currentDigit = originalStack.top();
            originalStack.pop();
            // 计算当前位翻倍后的值(考虑进位)
            resultStack.push((currentDigit * 2 + carry) % 10);
            carry = (currentDigit * 2 + carry) / 10; // 计算新的进位
            
            // 处理最高位可能的进位
            if(originalStack.empty() && carry != 0) {
                resultStack.push(carry);
                ListNode* newNode = new ListNode(); // 创建新节点存储进位
                tailNode->next = newNode; // 连接到链表尾部
            }
        }

        // 第三次遍历：将结果写回链表
        head = originalHead;
        while(!resultStack.empty()) {
            currentDigit = resultStack.top();
            resultStack.pop();
            head->val = currentDigit;
            head = head->next;
        }
        
        return originalHead; // 返回处理后的链表
    }
};

复杂度分析

‌时间复杂度‌：O(n)，需要三次线性遍历

‌空间复杂度‌：O(n)，使用两个栈存储数字

优化方向

‌递归解法‌：可以使用递归实现从低位到高位的处理

‌原地修改‌：尝试在不使用额外空间的情况下解决问题

‌数学优化‌：寻找数学规律减少计算步骤

总结

链表数字翻倍问题是栈结构和进位处理的典型应用场景，通过栈结构可以方便地实现从低位到高位的处理。理解这种解法有助于掌握链表操作和数字处理的核心技巧。