题解 | #链表相加(二)#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
	  // 创建两个栈，分别存储两个链表的结点，栈顶元素即链表表尾元素
        stack<ListNode*> st1;
        stack<ListNode*> st2;
	  // 将链表1的结点都放入栈st1中
        while(head1){
            st1.push(head1);
            head1 = head1->next;
        }
	  // 将链表2的结点都放入栈st2中
        while(head2){
            st2.push(head2);
            head2 = head2->next;
        }
	  // 标识flag表示结点值相加有无进位，由于初始为个位相加，初始化flag为0
        int flag = 0;
	  // 创建头尾结点，并将头节点指向尾结点
        ListNode* head = new ListNode(-1);
        ListNode* tail = NULL;
        head->next = tail;
	  // 栈顶结点相加，依次插入头尾结点之间
        while(!st1.empty() && !st2.empty()){
            int sum1 = st1.top()->val + st2.top()->val + flag;	// 注意要加上flag
            st1.pop(); st2.pop();	// 弹栈
		  // 根据有无进位，更新flag
            if(sum1 >= 10) flag = 1;
            else flag = 0;
		  // 创建临时结点，其值为相加后的个位数字
            ListNode* temp1 = new ListNode(sum1 % 10);
            temp1->next = tail;
            head->next = temp1;
            tail = temp1;	// 更新尾结点，尾结点需要向前推进，
        }
	  // 如果st2为空，而st1不为空，则继续处理st1中的结点
        while(!st1.empty()){
            int sum2 = st1.top()->val + flag;	// 不要忘记要加flag
            st1.pop();	// 弹栈
		  // 更新flag
            if(sum2 >= 10) flag = 1;
            else flag = 0;
            ListNode* temp2 = new ListNode(sum2 % 10);
            temp2->next = tail;
            head->next = temp2;
            tail = temp2;	// 更新尾结点
        }
	  // 如果st1为空，而st2不为空，则继续处理st2中的结点
        while(!st2.empty()){
            int sum2 = st2.top()->val + flag;	// 不要忘记要加flag
            st2.pop();	// 弹栈
		  // 更新flag
            if(sum2 >= 10) flag = 1;
            else flag = 0;
            ListNode* temp2 = new ListNode(sum2 % 10);
            temp2->next = tail;
            head->next = temp2;
            tail = temp2;	// 更新尾结点
        }
	  // 最后判断flag是否为1，为1表示有进位，需要再创建一个值为1的新结点，放在head和tail之间
        if(flag == 1){
            ListNode* temp3 = new ListNode(1);
            temp3->next = tail;
            head->next = temp3;
        }
        return head->next;	// 最后返回head的next指针
    }
};