题解 | #两个链表生成相加链表#

核心思想

######## 自主实现，连写带调花了近5个小时，思路很清晰，但是实现过程中，仍然遇到一些低级错误和容易忽略的东西

• 判任意链表为空，则返回另一个链表
• 反转两条链表 # 独立实现递归反转函数
• 分别计算两条链表的长度，后面会用，较重要
• 遍历反转后的短链表(长度相同时，随便一个)，同时每次一步往后移动
• 计算
  1. 当前两个链表的结点值相加
  2. 取余，取模
  3. 进位标记为1
• 更新相加后的值存到较长的链表当前指针 # 前面要抉择出来长短，且longHead, shortHead来区分
• 短链表遍历完后，判断是否有进位
  1. 有的话，就继续用来遍历剩余长链表，每次当前值+进位值
  2. 同计算-2
• 反转计算完的链表
• 遍历完剩余长链表后，再次判断是否有进位
  1. 有的就话需要申请新节点，值给长进位值（即1）
  2. 头插法到redHead上
• 最终返回最终链表头

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
struct ListNode * reverse(struct ListNode * head)
{
    // 空链表判断
    if(head == NULL)
    {
        return head;
    }
    // 递归结束条件
    if(head->next == NULL)
    {
        return head;
    }
    // 递归入栈
    struct ListNode * newHead;
    newHead = reverse(head->next);
    // 递归弹栈
    head->next->next = head;
    head->next = NULL;
    
    return newHead;
}

int get_len(struct ListNode * head)
{
    int len = 0;
    
    while(head != NULL)
    {
        head = head->next;
        len++;
    }
    
    return len;
}

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    // 任意为空，返回另一个
    if(head1 == NULL)
    {
        return head2;
    }
    if(head2 == NULL)
    {
        return head1;
    }
    // 分别计算出两个链表的长度，取长者后续作为存放结果的链表
    int len_head1 = get_len(head1);
    int len_head2 = get_len(head2);
    
    // 反转相加的两条链表
    struct ListNode * newHead1 = reverse(head1);
    struct ListNode * newHead2 = reverse(head2);
    // 
    struct ListNode * longHead = newHead1;
    struct ListNode * shortHead = newHead2;
    struct ListNode * retHead = NULL;
    // 反转后的两条链表从头到尾遍历，挨个相加，结果小于10，则直接存到当前结点，弱大于等于10， 则减去10，存下进位，差值存到当下结点
    if(len_head1 < len_head2)
    {
        longHead = newHead2;
        shortHead = newHead1;
    }
    
    retHead = longHead;
    int add_val = 0;
    int carry_val = 0;
    while(shortHead != NULL)
    {
        // calculate current long value.
        longHead->val = longHead->val + carry_val;
        add_val = longHead->val + shortHead->val;
        // position carry on
        carry_val = add_val / 10;
        longHead->val = add_val % 10;
        // move on
        longHead = longHead->next;
        shortHead = shortHead->next;
    }

    if(carry_val == 1)
    {
        while(longHead != NULL)
        {
            add_val = longHead->val + carry_val;
            carry_val = add_val / 10;
            longHead->val = add_val % 10;
            longHead = longHead->next;
        }
    }

    // reverse all above values.
    struct ListNode * ret = reverse(retHead);
    
    // need one more node to store position carry on.
    if(carry_val == 1)
    {
        struct ListNode * newNode = (struct ListNode *)malloc( sizeof( struct ListNode) );
        newNode->val = 1;
        newNode->next= ret;
        ret = newNode;
    }
    
    return ret;
}