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

/**
 思路：
 1. 先将链表逆序
 2. 然后将各个节点值相加
 3. 遍历链表大于10的减去10，向下个节点进一
 4. 再次将链表逆序
**/
#include <stdio.h>
#include <stdlib.h>
int countList(struct ListNode* head)
{// 统计链表长度
    int cnt = 0;
    while (head) {
        head = head->next;
        cnt++;
    }
    return cnt;
}
struct ListNode* reverse(struct ListNode* head)
{// 将链表逆序
    struct ListNode *p = NULL;
    struct ListNode *q = NULL;
    if(!head || !head->next)
    {
        return head;
    }
    p = head;
    q = head->next;
    head->next = NULL;
    while (p) {
        p = q->next;
        q->next = head;
        head = q;
        q = p;
    
    }
    return head;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {

    int cnt1 = countList(head1);
    int cnt2 = countList(head2);

    head1 = reverse(head1);
    head2 = reverse(head2);

    struct ListNode* t1 = NULL;
    struct ListNode* t2 = NULL;
    struct ListNode* head = NULL;
    if(cnt1>cnt2)
    {
        head = head1;
        t1 = head1;
        t2 = head2;
    }
    else {
        head = head2;
        t1 = head2;
        t2 = head1;
    }
    while (t1) {
        if(t2){
            t1->val = t1->val + t2->val;
            t1 = t1->next;
        }
        else {
            t1 = t1->next;
            break;
        }
        t2 = t2->next;
    }
    t1 = head;
    int flag = 0;
    int pre_flag = 0;
    int val = 0;
    while(t1)
    {
        val = t1->val + pre_flag;
        if(val>=10)
        {
            flag = 1;
        }
        else
        {
            flag = 0;
        }
        t1->val = val - (flag * 10) ;
        if(val>=10)
        {
            pre_flag = 1;
        }
        else
        {
            pre_flag = 0;
        }
        t1 = t1->next;
    }
    head = reverse(head);
    if(pre_flag)
    {
        struct ListNode * node = (struct ListNode *)malloc(sizeof(struct ListNode *));
        node->val = 1;
        node->next = head;
        head = node;
    }
    
    
    return head;
    
}