Leetcode No.2 Add Two Numbers

1.Description(题目描述)2. 思路分析3.代码示例3.1 C#版

1.Description(题目描述)

Leetcode原题传送门

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

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

(给出两列非空列表，每个列表总首节点到尾节点，分别存储了一个正整数的个位到最高位数字。计算两列列表所代表的的数字之和，并返回一个列表代表这个和，数字的存储方式与原列表相同)

2. 思路分析

模拟两数求和步骤，从最低位即两列列表的首节点，开始求和sum。sum加入sumList, 同时记录进位carry以加入到下一位求和。

3.代码示例

3.1 C#版

public ListNode AddTwoNumbers(ListNode l1, ListNode l2) { //create sumList ListNode head = new ListNode(-1), tail = null; //head and tail of sumList head.next = tail; //combine to a sumList ListNode curr = head, PosiL_1 = l1, PosiL_2 = l2; //3 pointers point to each list int carry = 0; //进位 //calculate sumList while(PosiL_1 != null || PosiL_2 != null) { //calculate sum int digit1 = (PosiL_1 != null) ? PosiL_1.val : 0; int digit2 = (PosiL_2 != null) ? PosiL_2.val : 0; int sum = digit1 + digit2 + carry; carry = sum / 10; //add listNode ListNode temp = new ListNode(sum % 10); temp.next = tail; curr.next = temp; curr = curr.next; //update pointers if (PosiL_1 != null) PosiL_1 = PosiL_1.next; if (PosiL_2 != null) PosiL_2 = PosiL_2.next; } //do not forget last carry if (carry > 0) curr.next = new ListNode(carry); return head.next; }