首页 > 代码库 > leetcode——Add Two Numbers 两个链表表示的正整数对其求和(AC)

leetcode——Add Two Numbers 两个链表表示的正整数对其求和(AC)

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

这个题想完成还是比较简单的,但是想完成高质量的结果还需要仔细斟酌,我介绍下我的低劣的AC代码,题目中给的示例两个数字是位数相同的,但是考虑到实际情况,肯定包含不等长的情况。为了不另开辟空间,我首先对两个链表进行了长度的比较,将长的数字和短的数字分别标记出来,然后之后的求和结果在长链表中进行更新覆盖,求和时需要考虑当较短数字叠加完成后仍有进位的情况,并且需要考虑最终进位一直到长数字的最高位仍有进位的情况,这时需要再添加一个链表节点,将最终的进位添加上去。代码如下:

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x),next(NULL)
	{}
 };
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if(l1 == NULL)
			return l2;
		else if(l2 == NULL)
			return l1;
		ListNode *l1Temp = l1;
		ListNode *l2Temp = l2;
		ListNode *longer,*shorter;
		int length1=0,length2=0,carry=0,temp=0;
		while(l1Temp != NULL)
		{
			length1++;
			l1Temp = l1Temp -> next;
		}
		while(l2Temp != NULL)
		{
			l2Temp = l2Temp->next;
			length2++;
		}
		if(length2 > length1)
		{
			longer = l2;
			shorter = l1;
		}
		else
		{
			longer = l1;
			shorter = l2;
		}
		l1Temp = longer;
		l2Temp = shorter;
		while(l1Temp != NULL && l2Temp != NULL)
		{
			if(carry != 0)
			{
				temp = l1Temp->val + l2Temp->val+carry;
				carry = 0;
			}
			else
			{
				temp = l1Temp->val + l2Temp->val;
			}
			if(temp > 9)
			{
				carry = temp / 10;
				l1Temp->val = temp%10;
			}
			else
			{
				l1Temp->val = temp;
			}
			l1Temp = l1Temp->next;
			l2Temp = l2Temp->next;
		}
		if(carry != 0)
		{
			while(l1Temp != NULL && carry != 0)
			{
				temp = l1Temp->val + carry;
				carry = temp / 10;
				l1Temp->val = temp % 10;
				l1Temp = l1Temp->next;
			}
			if(carry != 0)
			{
				ListNode *newNode = new ListNode(carry);
				l1Temp = longer;
				while(l1Temp->next != NULL)
					l1Temp = l1Temp->next;
				l1Temp->next = newNode;
			}
		}
		return longer;
    }
};