请你将两个数相加，并以相同形式返回一个表示和的链表。

Question

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

力扣 https://leetcode-cn.com/problems/add-two-numbers/

Answer 1

一、步骤

1、实现一个链表翻转；

2、实现两个链表相对位置的相加操作；

3、考虑进位；

二、源码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/*
l1 -> l2 -> l3 -> l4 -> l5

       |    |
      pre  now
*/

struct ListNode* reverseList(struct ListNode *l) {
    struct ListNode *pre = l, *now = l->next;
    struct ListNode *head = l;
    while(now) {
        pre->next = now->next;       // (1) 将 now 从链表中剥离出来；
        now->next = head;            // (2) 将 now 插入到之前的链表头之前；
        head = now;                  // (3) 让 now 成为新的链表头；
        
        now = pre->next;             // (4) now 也前进一格；
    }
    return head;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *l3 = NULL, *head, *tmp;
    int a, b, c, cap = 0;

    // l1 -> l2 上去
    while(l1 || l2 || cap) {
        a = l1 ? l1->val : 0;
        b = l2 ? l2->val : 0;
        c = a + b + cap;
        tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
        tmp->val = c % 10;
        tmp->next = l3;
        cap = c / 10;

        l3 = tmp;
        head = l3;
        
        if(l1) {
            l1 = l1->next;
        }
        if(l2) {
            l2 = l2->next;
        }
    }



    return reverseList(head);
}