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

/**
 * 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* reverseList(ListNode* head)//就地逆置法逆置链表,返回头结点
    {
        if(head==nullptr)
        {
            return nullptr;
        }
        else 
        {
            ListNode* pre=head;
            ListNode* cur=head->next;
            ListNode* temp;
            head->next=nullptr;
            while (cur!=nullptr) 
            {
                temp=cur->next;
                cur->next=pre;

                pre=cur;
                cur=temp;
            }
            return pre;
        }
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* p1=reverseList(head1);
        ListNode* p2=reverseList(head2);

        int carry=0;//初始进位为0
        int cursum=0;//当前位初始值为0
        ListNode* lastnode=nullptr;//结果链表的头结点
        while(p1!=nullptr||p2!=nullptr)
        {
            //加合当前位
            if(carry==1)
            {
                ++cursum;
            }
            if(p1!=nullptr)
            {
                cursum+=p1->val;
                p1=p1->next;
            }
            if(p2!=nullptr)
            {
                cursum+=p2->val;
                p2=p2->next;
            }

            //创建当前位结点
            cursum>=10?(carry=1,cursum-=10):(carry=0);
            ListNode* aNode=new ListNode(cursum);
            aNode->next=lastnode;
            lastnode=aNode;

            //恢复状态，carry不回复，carry保存的是下一个结点信息
            cursum=0;
        }

        if(carry==1)//是否需要增添位
        {
            ListNode* aNode=new ListNode(1);
            aNode->next=lastnode;
            lastnode=aNode;
        }

        return lastnode;

    }
};

以下算法来自牛客官方题解

算法描述：

• step 1：任意一个链表为空，返回另一个链表就行了，因为链表为空相当于0，0加任何数为0，包括另一个加数为0的情况。
• step 2：相继反转两个待相加的链表，反转过程可以参考反转链表。
• step 3：设置返回链表的链表头，设置进位carry=0.
• step 4：从头开始遍历两个链表，直到两个链表节点都为空且carry也不为1. 每次取出不为空的链表节点值，为空就设置为0，将两个数字与carry相加，然后查看是否进位，将进位后的结果（对10取模）加入新的链表节点，连接在返回链表后面，并继续往后遍历。
• step 5：返回前将结果链表再反转回来。