题解 | 链表相加(二)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        stack<int>st1;
        stack<int>st2;
        while(head1)
        {
            st1.push(head1->val);
            head1 = head1->next;
        }
        while(head2)
        {
            st2.push(head2->val);
            head2 = head2->next;
        }
        //
        int jin = 0, v = 0;
        ListNode* pre = nullptr;
        ListNode* t_node;
        while(!st1.empty() && !st2.empty())
        {
            int v1 = st1.top();            
            int v2 = st2.top();
            st1.pop(); st2.pop();
            v1 += (v2+jin);
            if(v1>=10) jin = 1;
            else jin = 0;
            v = v1%10;
            t_node = new ListNode(v);
            t_node->next = pre;
            pre = t_node;            
        }
        if(st1.empty() && st2.empty())
        {
            if(jin == 0) ;
            else{
                t_node = new ListNode(1);
                t_node->next = pre;
            }
            return t_node;
        } 
	  // st指向还有元素的栈，用于简化后面的代码
        stack<int>st;
        if(st1.empty()) st = st2;
        else st = st1;
        while(!st.empty())
        {
            int val = st.top(); st.pop();
            val += jin;
            if(val >= 10) jin = 1;
            else jin = 0;
            val %= 10;
            t_node = new ListNode(val);
            t_node -> next = pre;
            pre = t_node;
        }
        if(jin == 1)
        {
            t_node = new ListNode(1);
            t_node->next = pre;
        }
        return t_node;
    }
};

思路：链表末尾元素最后访问，但是加法运算中最先处理，后进先出想到用栈来模拟。

易错点：“最后一次进位”不能漏了处理，无论是两个链表长度相等，还是长度有差异，在处理完题目给链表的最后一个元素后，return结果前，还应该对进位标志符进行检验，若非零，则应新增一个值为一的节点。

后续代码可优化：本着“先完成，再完美”的原则，目前代码中尚存在不少重复的代码语句，后续可以整合成一个函数来统一。