LeetCode Add Two Numbers

LeetCode Add Two Numbers

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


本题考查链表的基本操作,类似于归并排序的merge过程。

第一版代码如下:

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

		ListNode *ans = new ListNode(0), *tail;
		tail = ans;
		int sum, carry=0;
		while (l1 && l2)
		{
			sum = l1->val + l2->val + carry;
			if (sum >= 10)
			{
				carry = 1;
				sum = sum % 10;
			}
			else
				carry = 0;

			ListNode *ln = new ListNode(0);
			tail->next = ln;
			tail = tail->next;
			tail->val = sum;
			l1 = l1->next;
			l2 = l2->next;
		}
		while (l1)
		{
			sum = l1->val + carry;
			if (sum >= 10)
			{
				carry = 1;
				sum = sum % 10;
			}
			else
				carry = 0;

			ListNode *ln = new ListNode(0);
			tail->next = ln;
			tail = tail->next;
			tail->val = sum;
			l1 = l1->next;
		}
		while (l2)
		{
			sum = l2->val + carry;
			if (sum >= 10)
			{
				carry = 1;
				sum = sum % 10;
			}
			else
				carry = 0;

			ListNode *ln = new ListNode(0);
			tail->next = ln;
			tail = tail->next;
			tail->val = sum;
			l2 = l2->next;
		}
		if (carry)
		{
			ListNode *ln = new ListNode(0);
			tail->next = ln;
			tail = tail->next;
			tail->val = 1;
		}
		return ans->next;
	}
};

本代码提交AC,用时40MS。

但是这个版本代码太长了,而且很多重复,不够优雅,翻了翻discuss,有个大神的代码很漂亮,摘录如下:

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

		ListNode *head = NULL, *prev = NULL;
		int sum, carry=0;
		while (l1 || l2)
		{
			int v1 = l1 ? l1->val : 0;
			int v2 = l2 ? l2->val : 0;
			sum = v1 + v2 + carry;
			carry = sum >= 10 ? 1 : 0;
			sum %= 10;
			ListNode *ln = new ListNode(sum);
			if (!head)
				head = ln;
			if (prev)
				prev->next = ln;
			prev = ln;
			
			l1 = l1 ? l1->next : NULL;
			l2 = l2 ? l2->next : NULL;
		}
		
		if (carry)
		{
			ListNode *ln = new ListNode(carry);
			prev->next = ln;
		}
		return head;
	}
};

本代码提交AC,用时36MS。

两个版本时间差不多,但是第二个版本看起来就很舒服。

One thought on “LeetCode Add Two Numbers

  1. Pingback: LeetCode Add Two Numbers II | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *