C# 写 LeetCode Medium #2 Add Two Numbers

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();

            l1.next = new ListNode();

            l1.next.next = new ListNode();

            ListNode l2 = new ListNode();

            l2.next = new ListNode();

            l2.next.next = new ListNode();

            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();

            ListNode head = l3;

            int sum = ;

            while (l1 != null || l2 != null)

            {

                sum = sum >  ?  : ;

                if (l1 != null)

                {

                    sum += l1.val;

                    l1 = l1.next;

                }

                if (l2 != null)

                {

                    sum += l2.val;

                    l2 = l2.next;

                }

                //存储在l3中

                l3.next = new ListNode(sum % );

                l3 = l3.next;

            }

            //判断最后一项是否和大于9，大于则需要再添加一个1.

            if (sum > )

            {

                l3.next = new ListNode();

            }

            return head.next;

        }

解析：

输入：ListNode类型的两个参数

输出：第一个节点。

思想：

　　循环链表中的每一位，sum存储两个链表对应位上的和。通过观察不难发现规律，如果上一位和大于9，则下一位初始sum为1，将结果存储在新的链表中。

　　最后一位上和大于9时，再多加一位，值为1。

时间复杂度：O(n)

巴特西

C# 写 LeetCode Medium #2 Add Two Numbers

最新文章

热门文章