[LeetCode] 2. Add Two Numbers

轉自LeetCode

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

<Solution>

這題是要相加兩個 link list，解題想法和 415. Add Stings 一樣，可以參考那篇文章

差別點只在於 data structure 不同，修改成操作 link list 的方式就可以了

code 如下

c++

	/**
	* 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 *dummy = new ListNode(-1);
	ListNode *currN = dummy;
	int sum = 0, carry = 0;
	while(l1 || l2) {
	int a = (l1) ? l1->val : 0;
	int b = (l2) ? l2->val : 0;
	sum = a + b + carry;
	carry = (sum > 9) ? sum / 10 : 0;
	sum = (sum > 9) ? sum % 10 : sum;
	currN->next = new ListNode(sum);
	currN = currN->next;
	if(l1) {
	l1 = l1->next;
	}
	if(l2) {
	l2 = l2->next;
	}
	}
	if(carry != 0) {
	currN->next = new ListNode(1);
	}
	return dummy->next;
	}
	};

view raw addTwoNumbers.cpp hosted with ❤ by GitHub

Java

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode dummy = new ListNode(-1);
	ListNode currN = dummy;
	int sum = 0, carry = 0;
	while(l1 != null || l2 != null) {
	int a = (l1 != null) ? l1.val : 0;
	int b = (l2 != null) ? l2.val : 0;
	sum = a + b + carry;
	carry = (sum > 9) ? sum / 10 : 0;
	sum = (sum > 9) ? sum % 10 : sum;
	currN.next = new ListNode(sum);
	currN = currN.next;
	if(l1 != null) {
	l1 = l1.next;
	}
	if(l2 != null) {
	l2 = l2.next;
	}
	}
	if(carry != 0) {
	currN.next = new ListNode(1);
	}
	return dummy.next;
	}
	}

view raw addTwoNumbers.java hosted with ❤ by GitHub