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

2019-02-27 11:51:15来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

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

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

您可以假设除了数字 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

原文链接:https://www.cnblogs.com/kk328/p/10440625.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:类型转换:static_cast、reinterpret_cast等

下一篇:#leetcode刷题之路5-最长回文子串