leetcode刷题第二天<两数相加>

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

首先是c++

最开始采用官方题解java该c++版本的，代码如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* p = l1;
        ListNode* q = l2;
        ListNode* curr = dummyHead;
        int carry = 0;
        while (p != 0 || q != 0) {
            int x = (p != 0) ? p->val : 0;
            int y = (q != 0) ? q->val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
            if (p != 0) p = p->next;
            if (q != 0) q = q->next;
        }
        if (carry > 0) {
            curr->next = new ListNode(carry);
        }
        return dummyHead->next;
    }
};

思路为申请一个新的链表空间进行存储，然后分别进行链表的传递，接着判断链表的值与0的关系返回，最后求和，然后%10取余数，最后判断余数和和0的关系，然后返回即可

另外一种大佬解法

是申请两个链表的空间，然后如果链表不为空进行遍历相加，最后在判断链表和余数与9的关系，最后返回第二个链表空间。

代码如下

class Solution 
{
public:
   
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
{
        ListNode* list_head= new ListNode(0);
       
 ListNode* list_node=list_head;
        
while(1)
        
{
            int sum=list_node->val;
       
 if(l1)
       
 {
            sum+=l1->val;
            l1=l1->next;
        }
        
if(l2)
       
 {
            sum+=l2->val;
            l2=l2->next;
        }
     
   list_node->val=sum%10;
        if(l1||l2||sum>9)
        
{
            list_node->next=new ListNode(sum/10);
            
list_node=list_node->next;
        }
       
 else{
            break;
        }
    }
   
   return list_head;
    }
};

最后再用python走下

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        add_num = 0
        new_list = ListNode(0)
        cur = new_list
        cur1 = l1
        cur2 = l2
        while cur1 or cur2:
            if cur1 and cur2:
                value = cur1.val + cur2.val + add_num
            elif cur1:
                value = cur1.val + add_num
            elif cur2:
                value = cur2.val + add_num
                
            cur.next = ListNode(value % 10)
            add_num = 0
            if value > 9:
                add_num = 1
            cur = cur.next
            if cur1:
                cur1 = cur1.next
            if cur2:
                cur2 = cur2.next
        if add_num:
            cur.next = ListNode(add_num)
            cur = cur.next
        return new_list.next

c实现算法如下

int remainder   = 0;
    int integer     = 0;
    int sum         = 0;
    int l1_val      = 0;
    int l2_val      = 0;
    struct ListNode *l_end = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *l_head = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *l_node;
    struct ListNode *l1_p = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *l2_p = (struct ListNode *)malloc(sizeof(struct ListNode));
    
    l1_p = l1;
    l2_p = l2;

    /*尾插法，当前只有头结点，且为空*/
    l_head->next = NULL;
    l_end = l_head;
    
    while((l1_p != NULL) || (l2_p != NULL))
    {

        l1_val = (l1_p != NULL)?l1_p->val:0;
        l2_val = (l2_p != NULL)?l2_p->val:0;
        sum       = l1_val + l2_val + integer;
        remainder = sum %10;
   
        
        l_node = (struct ListNode *)malloc(sizeof(struct ListNode));
        l_node->next = NULL;
        l_node->val = remainder;
        l_end->next = l_node;
        l_end = l_node;
        
        if(l1_p != NULL)
        {
            l1_p = l1_p->next;
        }
        
        if(l2_p != NULL)
        {
            l2_p = l2_p->next;
        }

        integer   = sum /10;
  
    }
    
     if(integer > 0)
     {
        l_node = (struct ListNode *)malloc(sizeof(struct ListNode));
        l_node->next = NULL;
        l_node->val = integer;
        l_end->next = l_node;
        l_end = l_node;
     }
    
    return l_head->next;
    
}

用到了尾插法链接https://blog.csdn.net/lixiaogang_theanswer/article/details/61195907