欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【LeetCode】: 两数相加

程序员文章站 2022-06-19 19:38:20
...

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

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

示例:

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

思路:

1.要相加两个数,且这两个数在链表中逆序方式存储,所以我们就要是他们相对应的每一位相加,如下边所示:

   【LeetCode】: 两数相加

  • 要使对应的每位相加,则只需要遍历以下链表(用while循环可以完成)
  • 将每次对应的位数相加的数定义为 sum
  • 需要注意的是每位相加的时候会出现大于10的数这时候就需要进位,则设置这个进位数为 carry = sum / 10

2.在相加每位对应的数时我们需要注意以下几种情况:

           【LeetCode】: 两数相加

3.完成了以上的事情,就需要考虑循环条件了

  • 为了使链表遍历一遍就需要条件链表的下一个节点不为空   l->next !=NULL
  • 为了考虑到上边第三条出现的情况就得加一条条件 carry == 1

代码部分:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
int sum = 0;
	int carry = 0;
	struct ListNode* ret = l1;
	struct ListNode* ptr = l2;
	struct ListNode* new_Node = NULL;
    struct ListNode* cur = NULL;
    struct ListNode* pre = NULL;
	while ((ret != NULL || ptr != NULL) || carry == 1)
	{
		sum = 0;
		if (ret != NULL)
		{
			sum += ret->val;
			ret = ret->next;
		}

		if (ptr != NULL)
		{
			sum += ptr->val;

			ptr = ptr->next;
		}

                        
        if(carry != 0)
        {
            
            sum += 1;
            
        }

        if(sum>9)
		{
			carry = sum / 10;
		}
        else
            carry = 0;
	
		new_Node = (struct ListNode*)malloc(sizeof(struct ListNode));

		new_Node->val = sum % 10;
		new_Node->next = NULL;

		if(NULL == cur)
        {
            cur = new_Node;
            pre = new_Node;
        }

        else
        {
            pre->next = new_Node;
            pre = pre->next;
        }
	}


	return cur;
}

             

复杂度分析

  • 时间复杂度:O(max(m,n))假设上边两链表的长度分别为m,n,则时间复杂度为max(m,n)
  • 空间复杂度:O(max(m,n))则新链表的长度最大为max(m,n) + 1