【算法百题之二十九】两数相加

 

    大家好，我是Lampard~~

    很高兴又能和大家见面了，接下来准备系列更新的是算法题，一日一练，早日升仙！

 

    今天的问题是：

給出的结构体：

struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

思路：这道题是需一次遍历就可以解决问题，假设list1的长度是n，list2的长度m。len = min(n,m) 。 那么第len位相加的时候，主要是要细心考虑好几种情况：

• 不产生进位，那么只需要把第len个结点的next指针指向长的链表的len + 1的结点上就可以了
• 产生进位但是不需要构建新的结点。也就是说，假如list1 = ｛5， 5｝，list2 = ｛5，5，5，5｝，那么len是2，5 + 5产生进位1，但是这个进位会被list2的len + 1个结点5吃掉，不会再产生新的进位。这样的话我们就不需要新建一个结点来存储进位的值。我们的结果链表的长度还是max(n ,m)
• 产生进位但是需要构建新的结点。假如list1 = ｛5，5｝，list2 = ｛5, 5, 9, 9, 9｝,那么这个进位会一直和9相加，哪怕到list2的长度结束的时候还会产生一个1的进位，这个时候我们的1不能扔掉，我们就需要新建一个结点来存储这个进位1，此时我们的结果链表的长度就是max（n, m）+ 1

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
	ListNode result(0), *p = &result;
	int flag = 0;

	while (l1 || l2 || flag) {
		int tmp = 0;
		if (l1 != nullptr) tmp += l1->val;
		if (l2 != nullptr) tmp += l2->val;
		tmp += flag;

		flag = tmp / 10;    // 十进位
		tmp %= 10;          // 个位

		ListNode *next = l1 ? l1 : l2;
		if (next == nullptr) next = new ListNode(flag);
		next->val = tmp;

		p->next = next;
		p = p->next;

		if ((l1 == nullptr or l2 == nullptr) and flag == 0) {
			break;
		}

		l1 = l1 ? l1->next : nullptr;
		l2 = l2 ? l2->next : nullptr;
	}

	return result.next;
}

以上是按照思路这道题的解法，关键点有两个：

1. 数据替换而不要新建结点，我们的结果是要返回一个链表，我们每一位相加之后会得到想要的值，此时不要新建结点存储这个值，这样会浪费内存，我们直接把list1或list2的一个结点值替换掉然后使用就可以了。
2. 如果如果有一条链表已经在len的地方遍历完毕，而且没有进位的话，剩下的我们只要指向长链表len+1就可以了，就不用全部遍历长链表。

测试函数以及测试结果：

 

 

   OK，今天的博客就到这里，谢谢大家！！！