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

/**
 * 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  利用栈来实现
        //1、将两个链表长度求出来，合并为一个链表
        //2、将链表节点入栈，然后考虑进制输出
        ListNode *p,*q;
        auto *first=new ListNode(0);
        first->next=nullptr;
        stack<ListNode *>s;
		p=head1;
		q=head2;
        int len1=0,len2=0;
		while(p){
			len1++;
			p=p->next;
		}
		while(q){
			len2++;
			q=q->next;
		}
		p=len1>=len2?head1:head2;
		q=len1<len2?head1:head2;
		int n=abs(len1-len2);
		while(n){
			p=p->next;
			n--;
		}
        while(p){
            p->val+=q->val;
            p=p->next;
            q=q->next;
        }
        p=len1>=len2?head1:head2;
        while (p) {
            s.push(p);
            p=p->next;
        }
        while (!s.empty()) {
            ListNode *t=s.top();
            s.pop();
            if(t->val>=10){
                if(!s.empty()){
                    s.top()->val+=t->val/10;
                    t->val=t->val%10;
                }
                else{
                    auto *temp =new ListNode(t->val/10);
                    s.push(temp);
                    t->val=t->val%10;
                }
            }
            t->next=first->next;
            first->next=t;
        }
        return first->next;
    }
};