程序员代码面试指南 2.10：两个单链表生成相加链表

1、思路

• 先把两个链表反转，从低位开始相加；

• 相加完毕后，再将链表反转即可。

2、代码

list_node* reverseList(list_node* head)     //反转链表
{
    if (head == nullptr) return nullptr;
    auto pre = head, cur = head->next;
    
    while (cur)
    {
        auto ne = cur->next;
        cur->next = pre;
        pre = cur, cur = ne;
    }
    
    head->next = nullptr;
    return pre;
}

list_node* addList(list_node* head1, list_node* head2)
{
    list_node *dummy = new list_node(), *p = dummy;
    int carry = 0;                      //进位标志
    
    while (head1 || head2)
    {
        //链表不为空就将当前的两个节点的值加起来，为空就加0
        carry += (head1 == nullptr ? 0 : head1->val) + (head2 == nullptr ? 0 : head2->val);
        
        auto tmp = new list_node();
        tmp->val = carry % 10;
        
        //如果当前节点有进位，就取模后为1，没有进位就保持原值
        //p = p->next = xx 表示 p->next = xx, p = p->next两条语句的组合
        p = p->next = tmp;
        carry /= 10;                    //如果有进位，则carry余1， 没有进位则carry重置为0
        
        if (head1) head1 = head1->next;
        if (head2) head2 = head2->next;
    }
    
    if (carry)                          //判断最高位是否有进位，有的话就再追加一个1即可
    {
        auto tmp = new list_node();
        tmp->val = 1;
        p->next = tmp;
    }
    
    return dummy->next;
}

list_node * add_list(list_node * head1, list_node * head2)
{
    if (head1 == nullptr || head2 == nullptr) return head1 == nullptr ? head2 : head1;
    
    head1 = reverseList(head1), head2 = reverseList(head2); //反转两条链表
    return reverseList(addList(head1, head2));              //计算出结果后再反转一次
}