【LeetCode】Add Two Numbers(两数相加)

这道题是LeetCode里的第2道题。

题目要求：

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

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

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

示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

这道题的条件判断很简单，如下：

1.是否为尾节点

2.是否产生进位

3.是否等于9

4.是否需要拓展空间

代码如下：

/**

 * 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 *p = l1, *q = l2;

	int add, carry = 0;//carry标志进位

	while (1) {

		add = p->val + q->val + carry;

		p->val = add % 10;

		if (add > 9)carry = 1;

		else carry = 0;

		if (p->next == NULL || q->next == NULL)break;

		p = p->next;

		q = q->next;

	}

//这里就相当于是一个链表只有一个节点，另一个链表加上这个一个节点的数值

	if (p->next) {//list1

		p = p->next;

		q = p;

		while (carry) {//是否需要进位

			if (q->val == 9) {//是否等于9

				if (q->next == NULL) {//是否是最后一个节点

					q->val = 0;

					q->next = (ListNode*)malloc(sizeof(ListNode));

					q->next->val = 1;

					q->next->next = NULL;

					break;

				}

				q->val = 0;

				q = q->next;}

			else {q->val++;carry = 0;}

		}

		return l1;

	}

	if (q->next) {//list2

		q = q->next;

		l2 = q;

		while (carry) {

			if (q->val == 9) {

				if (q->next == NULL) {

					q->val = 0;

					q->next = (ListNode*)malloc(sizeof(ListNode));

					q->next->val = 1;

					q->next->next = NULL;

					break;

				}

				q->val = 0;

				q = q->next;}

			else {q->val++;carry = 0;}

		}

		p->next = l2;

		return l1;

	}

	if (carry) {

		q = (ListNode*)malloc(sizeof(ListNode));

		q->next = NULL;

		q->val = 1;

		p->next = q;

	}

	return l1;

    }

};

运行结果：

个人总结：

在设计算法初期，造成了许多代码的累赘，以上代码是经过优化后得到的。但是在这里两个if条件中还是会有代码的重复，但能够做出来我就已经很开心了。(＾－＾)V

巴特西

【LeetCode】Add Two Numbers(两数相加)

这道题是LeetCode里的第2道题。

题目要求：

代码如下：

运行结果：

个人总结：

最新文章

热门文章