2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse orderand each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
代码：
static void Main(string[] args) { ListNode l1 = new ListNode(3); l1.next = new ListNode(6); l1.next.next = new ListNode(9); ListNode l2 = new ListNode(7); l2.next = new ListNode(0); l2.next.next = new ListNode(3); var res= addTwoNumbers(l1, l2); while (res != null) { Console.Write(res.val); res = res.next; } Console.ReadKey(); } public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; } } public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode l3 = new ListNode(0); ListNode head = l3; int sum = 0; while (l1 != null || l2 != null) { sum = sum > 9 ? 1 : 0; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } //存储在l3中 l3.next = new ListNode(sum % 10); l3 = l3.next; } //判断最后一项是否和大于9，大于则需要再添加一个1. if (sum > 9) { l3.next = new ListNode(1); } return head.next; }
解析：
输入：ListNode类型的两个参数
输出：第一个节点。
思想：
循环链表中的每一位，sum存储两个链表对应位上的和。通过观察不难发现规律，如果上一位和大于9，则下一位初始sum为1，将结果存储在新的链表中。
最后一位上和大于9时，再多加一位，值为1。
时间复杂度：O(n)
C# 写 LeetCode Medium #2 Add Two Numbers
原文：https://www.cnblogs.com/s-c-x/p/10153019.html