问题描述

给定两个用链表表示的整数，每个节点包含一个数位。这些数位时反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和并用链表形式返回结果.
例如：364 表示为 4->6->3，789表示为 9->8->7，
输入链表4->6->3 和 9->8->7
返回链表 3->5->1->1 （表示1153的链表）

解

namespace LinkListAdd
{
    class Program
    {
        static void Main(string[] args)
        {
            LinkedList<int> a = new LinkedList<int>();
            a.AddLast(4);
            a.AddLast(6);
            a.AddLast(3);
            LinkedList<int> b = new LinkedList<int>();
            b.AddLast(9);
            b.AddLast(8);
            b.AddLast(7);

            LinkedList<int> r = LinkAdd(a, b);
            LinkedListNode<int> rNode = r.First;
            while (rNode != null)
            {
                Console.WriteLine(rNode.Value);
                rNode = rNode.Next;
            }
        }

        static LinkedList<int> LinkAdd(LinkedList<int> a,LinkedList<int> b)
        {
            LinkedListNode<int> tempA = a.First;
            LinkedListNode<int> tempB = b.First;

            LinkedList<int> result = new LinkedList<int>();

            //进位数（两个相同位的数相加后 需要进位的数）
            int addForward = 0;

            //其中一个链表不为空 或者 进位数不为0，当两个数相加完毕后，可能链表为空但还有进位的数
            while (tempA != null || tempB != null || addForward!=0)
            {
                int numA = tempA != null ? tempA.Value : 0;
                int numB = tempB != null ? tempB.Value : 0;

                //相加
                int currentNum = numA + numB + addForward;

                //进位
                if (currentNum > 9)
                {
                    addForward = currentNum /10;
                    currentNum %= 10;
                }//不进位
                else
                {
                    addForward = 0;
                }
                //进表
                result.AddLast(new LinkedListNode<int>(currentNum));

                //链表递进
                tempA = tempA!= null ? tempA.Next : null;
                tempB = tempB!= null ? tempB.Next : null;
            }
            return result;
        }
    }
}