我们知道两个数相加是从低位往高位逐位相加再看进位。
所以可以先把两个链表反转，这样就不用管链表到底多长。
定义两个指针分别指向反转后的链表头。假设链表1,是用于存放相加后的结果。
p指向head1，q指向head2；
再定义一个变量 k——表示当前是否有进位。
如果两个链表一样长，结束是需要判断是否有进位。
如果两个链表不一样长，进行到某一个链表结束时，判断到底是p先结束还是q先结束，q指针指向的下一个是未结束的那个。
然后继续遍历p，只有当p->next==NULL或进位标示为0就结束。
最后如果是遍历完链表结束的循环，就需要判断当前是否有进位。
这样做的时间复杂度为O(n)，n取决于最长的链表长度，空间复杂度为O(1),只有常数个变量。 

/**
 * 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) {
        // write code here
        if(head1==NULL) return head2;
        if(head2==NULL) return head1;
        ListNode *p,*q;
        head1=ReveseList(head1);
        head2=ReveseList(head2);
        p=head1;
        q=head2;
        int k=0;
        int x=0;
        while(p->next!=NULL&&q->next!=NULL) {
            x=p->val+q->val+k;
            p->val=(x>=10)?x%10:x;
            k=(x>=10)?1:0;
            p=p->next;
            q=q->next;
        }
        x=p->val+q->val+k;
        p->val=(x>=10)?x%10:x;
        k=(x>=10)?1:0;
        if(p->next==NULL&&q->next==NULL&&k){
                ListNode *l=(ListNode*)malloc(sizeof(ListNode));
                l->val=1;
                l->next=NULL;
                p->next=l;
        }
        else p->next=(p->next==NULL)?q->next:p->next;
        while(p->next!=NULL&&k) {
            p=p->next;
            x=p->val+k;
            p->val=(x>=10)?x%10:x;
            k=(x>=10)?1:0;
        }
        if(p->next==NULL&&k) {
            ListNode *l=(ListNode*)malloc(sizeof(ListNode));
            l->val=1;
            l->next=NULL;
            p->next=l;
        }
        head1=ReveseList(head1);
        return head1;
    }
public: ListNode* ReveseList(ListNode* Head) {
        ListNode* p=NULL;
        ListNode* q=NULL;
        while(Head!=NULL)
        {
            q=Head;
            Head=Head->next;
            q->next=p;
            p=q;
        }
        return p;
    }
};