题目要求不能对原链表进行操作，因此直接把链表都逆过来是不行的（该问题的I问题就是逆过来的）。
但是不逆过来不好做，因此计算的时候逆过来，或者逆过来再计算。
方法一：
计算的时候逆过来：新建一个链表，在计算对应位和的时候逆过来。
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *p, *q; p=l1; int n1=0; while(p){++n1; p=p->next;} p=l2; int n2=0; while(p){++n2;p=p->next;} if (n1<n2){p=l1; l1=l2; l2=p; swap(n1,n2);} ListNode *head=new ListNode(0); head->next=NULL; p=l1; q=l2; for (int i=0;i<n1-n2;++i){ addtohead(p->val,head); p=p->next; } for (int i=0;i<n2;++i){ addtohead(p->val+q->val,head); p=p->next; q=q->next; } p=head->next; ListNode *res=new ListNode(0); res->next=NULL; int carry=0; while(p){ p->val+=carry; carry= p->val / 10; addtohead(p->val%10,res); p = p->next; } if(carry) addtohead(carry,res); return res->next; } void addtohead(int num, ListNode *head){ ListNode *tmp=new ListNode(num); tmp->next = head->next; head->next = tmp; } };
方法二：
逆过来再计算：不能对原链表操作，那我们可以建立一个数组，倒序访问，或者利用栈，直接倒序计算：
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack<int> s1,s2; ListNode *p=l1; while(p) s1.push(p->val), p=p->next; p=l2; while(p) s2.push(p->val), p=p->next; ListNode *head=new ListNode(0); head->next=NULL; int carry=0; while(!s1.empty()||!s2.empty()){ int tmp=carry; if (!s1.empty()) tmp+=s1.top(), s1.pop(); if (!s2.empty()) tmp+=s2.top(), s2.pop(); carry = tmp/10; tmp %= 10; addtohead(tmp,head); } if(carry) addtohead(carry,head); return head->next; } void addtohead(int num, ListNode *head){ ListNode *tmp=new ListNode(num); tmp->next = head->next; head->next = tmp; } };
原文：https://www.cnblogs.com/hankunyan/p/9142527.html