链表求和-c语言

81 阅读 0 评论 54 点赞

我是靠谱客的博主清秀蜜蜂，最近开发中收集的这篇文章主要介绍链表求和-c语言，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链表求和

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912

进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912

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

int f(struct ListNode* l1){
 
    int t=1;
    while(l1){
  //      printf("dfa");
    printf(" --%d",l1->val);
      
        sum=sum+l1->val*t;
        t=t*10;
        l1=l1->next;
    }
    //    printf("dfa");
    return sum;

}
struct ListNode*  f2(int val){
    struct ListNode *p=(struct ListNode*)malloc(sizeof(struct ListNode));
     struct ListNode *L;

    p->next=NULL;
    if(val==0){
          L=(struct ListNode*)malloc(sizeof(struct ListNode));
        L->val=0;
      
        L->next=p->next;
        p->next=L;

    }
    while(val){
        L=(struct ListNode*)malloc(sizeof(struct ListNode));
        L->val=val%10;
        val=val/10;
        L->next=p->next;
        p->next=L;

    }
   f_verser(p);
    return p;

}
void f_verser(struct ListNode*p){
    struct ListNode *L,*s;
    L=p->next;
    p->next=NULL;
    while(L){
        s=L;
        L=L->next;
        s->next=p->next;
        p->next=s;
    }
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int s1=f(l1);
    int s2=f(l2);
    struct ListNode *p;
    printf(" l1 %d",s1);

   // printf("%d ",s1+s2);
    p=f2(s1+s2);
    return p->next;
   
 

}

下面有一个更好的解法：
思路与算法

由于输入的两个链表都是反向存放数字的位数的，因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2n_1,n_2n1,n2，进位值为 carrytextit{carry}carry，则它们的和为 n1+n2+carryn_1+n_2+textit{carry}n1+n2+carry；其中，答案链表处相应位置的数字为 (n1+n2+carry) mod 10(n_1+n_2+textit{carry}) bmod 10(n1+n2+carry)mod10，而新的进位值为 ⌊n1+n2+carry10⌋Biglfloordfrac{n_1+n_2+textit{carry}}{10}Bigrfloor⌊10n1+n2+carry⌋。

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 000 。

此外，如果链表遍历结束后，有 carry>0textit{carry} > 0carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carrytextit{carry}carry。

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *head = NULL, *tail = NULL;
    int carry = 0;
    while (l1 || l2) {
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int sum = n1 + n2 + carry;
        if (!head) {
            head = tail = malloc(sizeof(struct ListNode));
            tail->val = sum % 10;
            tail->next = NULL;
        } else {
            tail->next = malloc(sizeof(struct ListNode));
            tail->next->val = sum % 10;
            tail = tail->next;
            tail->next = NULL;
        }
        carry = sum / 10;
        if (l1) {
            l1 = l1->next;
        }
        if (l2) {
            l2 = l2->next;
        }
    }
    if (carry > 0) {
        tail->next = malloc(sizeof(struct ListNode));
        tail->next->val = carry;
        tail->next->next = NULL;
    }
    return head;
}