用 TDD 來(lái)練習(xí)完成 LeetCode 的第 2 題姥宝，題目描述如下。

LeetCode 2. Add Two Numbers

LeetCode 第 2 題 題目解釋?zhuān)航o兩個(gè) ListNode 分別為 **L1 **與 L2界轩，ListNode 的概念就像 LinkedList
的 Node 一樣，可以代表一串正整數(shù)。當(dāng) **L1 **+ L2 代表兩串正整數(shù)相加肩狂，加完的 ListNode 應(yīng)為兩串正整數(shù)相加的結(jié)果。

其實(shí)這題目就是兩個(gè)大數(shù)正整數(shù)相加的資料結(jié)構(gòu)設(shè)計(jì)方式姥饰。兩個(gè)數(shù)字相加傻谁，不管宣告成 int32 或是 long 都有其表示範(fàn)圍的極限，超過(guò)就會(huì)出現(xiàn) overflow exception列粪，透過(guò)將數(shù)字拆成整數(shù)串列审磁，每一位數(shù)字相加谈飒，若有進(jìn)位情況，則將進(jìn)位的數(shù)字 1 帶往下一個(gè) Node态蒂，最後將每一個(gè)數(shù)字串起來(lái)杭措，代表相加完的結(jié)果即可。所以钾恢，L1 與 L2 分別代表倒序排列的正整數(shù)瓤介，相加完的結(jié)果，只需要再倒序回來(lái)赘那，即為兩正整數(shù)相加的實(shí)際結(jié)果刑桑。

前言

這道題我用 TDD 練習(xí)了兩次，第一次 TDD 的過(guò)程募舟，最後雖然完成了祠斧，但我覺(jué)得測(cè)試案例的設(shè)計(jì)順序不對(duì)。應(yīng)先針對(duì)單一個(gè)數(shù)字的所有情況都設(shè)計(jì)完畢後拱礁，才考慮兩個(gè)數(shù)字的情況琢锋，最後針對(duì)三個(gè)數(shù)字的情況才重構(gòu)成迴圈或遞迴。

本篇文章將以第二次 TDD 的歷程為基準(zhǔn)呢灶，目的是用以呈現(xiàn) TDD 時(shí)吴超，

1. 對(duì)測(cè)試程式的重構(gòu)，是如何提昇 TDD 的生產(chǎn)力鸯乃。
2. 設(shè)計(jì)測(cè)試案例的順序鲸阻，是如何 baby step 的方式堆砌/雕塑出 production code。
3. 重構(gòu)時(shí)缨睡，透過(guò)一些簡(jiǎn)單的手法鸟悴，例如 introduce variable 或 inline variable 來(lái)找到重複的 pattern，再將其抽象出來(lái)共用。

Step 1, 第一個(gè)紅燈，L1_is_5_and_L2_is_4_should_return_9

測(cè)試案例代表性：L1 長(zhǎng)度為 1绿贞，L2 長(zhǎng)度為 1，沒(méi)有進(jìn)位

測(cè)試代碼：

        [TestMethod]
        public void L1_is_5_and_L2_is_4_should_return_9()
        {
            var l1 = new ListNode(5);
            var l2 = new ListNode(4);
            var expected = new ListNode(9);

            Assert.AreEqual(expected.val, new Solution().AddTwoNumbers(l1, l2).val);
        }

生產(chǎn)代碼：

    public class Solution
    {
        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            throw new NotImplementedException();
        }
    }

    public class ListNode
    {
        public int val;
        public ListNode next;

        public ListNode(int x)
        {
            val = x;
        }
    }

Step 2, 第一個(gè)綠燈震贵，L1.val + L2.val 以通過(guò)綠燈

生產(chǎn)代碼：

        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            return new ListNode(l1.val + l2.val);
        }

Step 3, 重構(gòu)測(cè)試程式，讓後面的測(cè)試案例用最少的 effort 撰寫(xiě)

將 assertion 的部分抽取出來(lái)為 AssertResult()水评，測(cè)試代碼如下：

        [TestMethod]
        public void L1_is_5_and_L2_is_4_should_return_9()
        {
            var l1 = new ListNode(5);
            var l2 = new ListNode(4);
            var expected = new ListNode(9);

            AssertResult(expected, l1, l2);
        }

        private static void AssertResult(ListNode expected, ListNode l1, ListNode l2)
        {
            Assert.AreEqual(expected.val, new Solution().AddTwoNumbers(l1, l2).val);
        }

這樣後面的測(cè)試案例猩系，Assert 的部分只需要輸入 AR + tab 即可省去原本要打很多字的工作。

Step 4, 新增 ListNode.All() 的測(cè)試案例之碗，以輔助 ListNode 多個(gè) next 值的驗(yàn)證

替 ListNode 增加一個(gè) All() 的方法蝙眶，其本意其實(shí)是組出 ListNode 的 LinkedList。這一個(gè)方法與 LeetCode 需求無(wú)關(guān)，也與 Solution 本身無(wú)關(guān)幽纷。但 ListNode 有了 All() 的方法式塌，對(duì)後續(xù)驗(yàn)證 ListNode 多個(gè)值有幫助。

ListNode.All() 測(cè)試代碼：

    [TestClass]
    public class ListNodeTests
    {
        [TestMethod]
        public void Test_All_ListNode_is_4_1()
        {
            var node = new ListNode(4);
            node.next = new ListNode(1);

            var expected = new List<int>() { 4, 1 };
            expected.ToExpectedObject().ShouldEqual(node.All());
        }
    }

生產(chǎn)代碼：

    public class ListNode
    {
        public int val;
        public ListNode next;

        public ListNode(int x)
        {
            val = x;
        }

        public IEnumerable<int> All()
        {
            var result = new List<int>();
            result.Add(this.val);

            if (this.next != null)
            {
                result.AddRange(next.All());
            }

            return result;
        }
    }

Step 5, 重構(gòu)測(cè)試程式友浸，改用 ListNode.All() 做 Assertion

測(cè)試代碼調(diào)整如下：

        private static void AssertResult(ListNode expected, ListNode l1, ListNode l2)
        {
            expected.All().ToExpectedObject().ShouldEqual(new Solution().AddTwoNumbers(l1, l2).All());
        }

Step 6, 新增一個(gè)失敗測(cè)試案例：L1_is_8_and_L2_is_6_should_return_4_1

測(cè)試案例代表性：L1 長(zhǎng)度為 1峰尝，L2 長(zhǎng)度為 1，相加進(jìn)位的情況收恢。

測(cè)試代碼如下：

        [TestMethod]
        public void L1_is_8_and_L2_is_6_should_return_4_1()
        {
            var l1 = new ListNode(8);
            var l2 = new ListNode(6);
            var expected = new ListNode(4);
            expected.next = new ListNode(1);

            AssertResult(expected, l1, l2);
        }

Step 7, 通過(guò)測(cè)試案例武学，當(dāng) L1.val + L2.val >= 10 時(shí)，需新增 next ListNode

生產(chǎn)代碼差異如下：

生產(chǎn)代碼迭代差異

加總新 Node 的值需 mod 10伦意，而如果加總值超過(guò) 10火窒，進(jìn)位 1 到 next ListNode 的值中。

Step 8, 重構(gòu)測(cè)試案例驮肉，使得建立多層 ListNode 更簡(jiǎn)便

可以看到原本要新增 ListNode 代表 {4,1} 得一直塞 next ListNode熏矿，這樣撰寫(xiě)測(cè)試案例實(shí)在太麻煩，所以我們希望傳入一個(gè) int[] 就可以迅速建立一個(gè)完整的 ListNode 使用离钝。

調(diào)整完測(cè)試代碼如下：

        [TestMethod]
        public void L1_is_8_and_L2_is_6_should_return_4_1()
        {
            var l1 = new ListNode(8);
            var l2 = new ListNode(6);

            var expected = CreateListNodes(new int[] { 4, 1 });

            AssertResult(expected, l1, l2);
        }

        private static ListNode CreateListNodes(int[] nums)
        {
            if (nums.Length == 0)
            {
                return null;
            }

            var listNode = new ListNode(nums[0]);

            var currentNode = listNode;
            for (int i = 1; i < nums.Length; i++)
            {
                currentNode.next = new ListNode(nums[i]);
                currentNode = currentNode.next;
            }

            return listNode;
        }

Step 9, 新增一個(gè)失敗的測(cè)試案例：L1_is_5_4_and_L2_is_3_should_return_8_4

測(cè)試案例代表性：L1 長(zhǎng)度來(lái)到 2票编，L2 長(zhǎng)度仍為 1，沒(méi)有進(jìn)位

測(cè)試代碼如下：

        [TestMethod]
        public void L1_is_5_4_and_L2_is_3_should_return_8_4()
        {
            var l1 = CreateListNodes(new int[] { 5, 4 });

            var l2 = CreateListNodes(new int[] { 3 });

            var expected = CreateListNodes(new int[] { 8, 4 });

            AssertResult(expected, l1, l2);
        }

Step 10, 通過(guò)測(cè)試案例：新增判斷 L1.next 是否有值卵渴，若有慧域，則也需新增 next ListNode

生產(chǎn)代碼差異如下：

生產(chǎn)代碼迭代差異

【注意】
通常在這步驟，一般開(kāi)發(fā)人員就會(huì)把 rootSum >=10 與 L1.next !=null 與 L2.next != null 一併寫(xiě)完浪读，而 TDD 的 baby step 就是用最小的異動(dòng)昔榴，最簡(jiǎn)單的生產(chǎn)代碼，恰好地通過(guò)眼前的紅燈瑟啃。但心裡很清楚论泛，等等要新增一個(gè)測(cè)試案例是 L2.next != null 以及進(jìn)位的測(cè)試案例。別急蛹屿，讓子彈飛一會(huì)兒。

Step 11, 新增一個(gè)失敗測(cè)試案例：L1_is_5_and_L2_is_3_4_should_return_8_4

測(cè)試案例代表性：換 L2 長(zhǎng)度為 2岩榆，沒(méi)有進(jìn)位的情境

測(cè)試代碼：

        [TestMethod]
        public void L1_is_5_and_L2_is_3_4_should_return_8_4()
        {
            var l1 = new ListNode(5);
            var l2 = CreateListNodes(new int[] { 3, 4 });
            var expected = CreateListNodes(new int[] { 8, 4 });
            AssertResult(expected, l1, l2);
        }

Step 12, 通過(guò)測(cè)試案例：增加判斷 L2.next 是否有值错负，若有，也需新增 next ListNode

生產(chǎn)代碼差異：

生產(chǎn)代碼迭代差異

Step 13, 重構(gòu)生產(chǎn)代碼：整理需新增 next ListNode 的判斷邏輯

當(dāng)發(fā)生進(jìn)位情況勇边，或是 L1.next 與 L2.next 其中一個(gè)有值犹撒，都應(yīng)新增 next ListNode

生產(chǎn)代碼重構(gòu)差異如下：

生產(chǎn)代碼迭代

Step 14, 重構(gòu)生產(chǎn)代碼：Introduce Variable，將判斷式的 condition 以 variable 呈現(xiàn)

生產(chǎn)代碼差異如下：

生產(chǎn)代碼迭代差異

Step 15, 新增一個(gè)失敗測(cè)試案例：L1_is_5_4_3_and_L2_is_2_should_return_7_4_3

測(cè)試案例代表性：長(zhǎng)度為 2 的都已經(jīng)處理完畢粒褒，接下來(lái)?yè)Q L1 長(zhǎng)度為 3识颊，沒(méi)有進(jìn)位的情況。

測(cè)試代碼：

        [TestMethod]
        public void L1_is_5_4_3_and_L2_is_2_should_return_7_4_3()
        {
            var l1 = CreateListNodes(new int[] {5, 4, 3});
            var l2 = new ListNode(2);
            var expected = CreateListNodes(new int[] {7, 4, 3});
            AssertResult(expected, l1, l2);
        }

Step 16, 通過(guò)測(cè)試案例：判斷 L1.next.next 是否有值，若有值祥款，需新增 ListNode.next.next

生產(chǎn)代碼差異如下：

生產(chǎn)代碼迭代差異

這一步走得有點(diǎn)髒清笨，卻是剛好滿(mǎn)足測(cè)試案例。我們一樣不急刃跛，L2 的判斷與進(jìn)位的判斷抠艾，等後面新增測(cè)試案例時(shí)，自然就會(huì)在生產(chǎn)代碼中加入桨昙。

Step 17, 新增一個(gè)失敗測(cè)試案例：L1_is_5_and_L2_is_1_2_3_should_return_6_2_3

測(cè)試案例代表性：L2 長(zhǎng)度為 3检号，無(wú)進(jìn)位。逼出生產(chǎn)代碼需判斷 L2.next.next 是否有值

測(cè)試代碼：

        [TestMethod]
        public void L1_is_5_and_L2_is_1_2_3_should_return_6_2_3()
        {
            var l1 = new ListNode(5);
            var l2 = CreateListNodes(new int[] { 1, 2, 3 });
            var expected = CreateListNodes(new int[] { 6, 2, 3 });
            AssertResult(expected, l1, l2);
        }

通過(guò)測(cè)試的生產(chǎn)代碼：

        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            var rootSum = l1.val + l2.val;
            var rootVal = rootSum % 10;

            var result = new ListNode(rootVal);

            var needCarry = rootSum >= 10;
            var hasL1Next = l1.next != null;
            var hasL2Next = l2.next != null;

            if (needCarry || hasL1Next || hasL2Next)
            {
                var carry = needCarry ? 1 : 0;
                var l1NextVal = l1.next?.val ?? 0;
                var l2NextVal = l2.next?.val ?? 0;

                result.next = new ListNode(carry + l1NextVal + l2NextVal);

                if (hasL1Next && l1.next.next != null)
                {
                    result.next.next = new ListNode(l1.next.next.val);
                }
                else if(hasL2Next && l2.next.next != null)
                {
                    result.next.next = new ListNode(l2.next.next.val);
                }
            }

            return result;
        }

Step 18, 新增一個(gè)失敗的測(cè)試案例：L1_is_5_4_and_L2_is_2_8_should_return_7_2_1

測(cè)試案例代表性：L1 與 L2 長(zhǎng)度為 2蛙酪，有進(jìn)位的情況齐苛。

測(cè)試代碼：

        [TestMethod]
        public void L1_is_5_4_and_L2_is_2_8_should_return_7_2_1()
        {
            var l1 = CreateListNodes(new int[] { 5, 4 });
            var l2 = CreateListNodes(new int[] { 2, 8 });
            var expected = CreateListNodes(new int[] { 7, 2, 1 });
            AssertResult(expected, l1, l2);
        }

Step 19, 調(diào)整生產(chǎn)代碼，通過(guò)所有測(cè)試

生產(chǎn)代碼：

        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            var rootSum = l1.val + l2.val;
            var rootVal = rootSum % 10;

            var result = new ListNode(rootVal);

            var needCarry = rootSum >= 10;
            var hasL1Next = l1.next != null;
            var hasL2Next = l2.next != null;

            if (needCarry || hasL1Next || hasL2Next)
            {
                var carry = needCarry ? 1 : 0;
                var l1NextVal = l1.next?.val ?? 0;
                var l2NextVal = l2.next?.val ?? 0;

                var nextSum = carry + l1NextVal + l2NextVal;
                var nextVal = nextSum % 10;

                result.next = new ListNode(nextVal);

                var needCarry_2 = nextSum >= 10;
                var hasL1Next_2 = hasL1Next && l1.next.next != null;
                var hasL2Next_2 = hasL2Next && l2.next.next != null;

                if (needCarry_2 || hasL1Next_2 || hasL2Next_2)
                {
                    var carry_2 = needCarry_2 ? 1 : 0;
                    var l1Next_2_Val = l1.next?.next?.val ?? 0;
                    var l2Next_2_Val = l2.next?.next?.val ?? 0;
                    result.next.next = new ListNode(carry_2 + l1Next_2_Val + l2Next_2_Val);
                }
            }

            return result;
        }

就像第一次判斷是否要新增 next ListNode 一樣桂塞，只是這次是判斷是否新增 next.next凹蜂。

Step 20, 重構(gòu)生產(chǎn)代碼：新增多餘的代碼，讓 next 的處理與 next.next 的處理長(zhǎng)得一樣

我們很清楚藐俺，next 的判斷與處理炊甲，應(yīng)該與 next.next 相同，因此動(dòng)點(diǎn)手腳欲芹，讓兩者的代碼長(zhǎng)得一樣卿啡，以便後續(xù)重構(gòu)抽象的處理

生產(chǎn)代碼差異：

生產(chǎn)代碼迭代差異

生產(chǎn)代碼：

        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            var carry_0 = 0;
            var l1Val = l1.val;
            var l2Val = l2.val;

            var rootSum = carry_0 + l1Val + l2Val;
            var rootVal = rootSum % 10;

            var result = new ListNode(rootVal);

            var needCarry = rootSum >= 10;
            var hasL1Next = l1.next != null;
            var hasL2Next = l2.next != null;

            if (needCarry || hasL1Next || hasL2Next)
            {
                var carry = needCarry ? 1 : 0;
                var l1NextVal = l1.next?.val ?? 0;
                var l2NextVal = l2.next?.val ?? 0;

                var nextSum = carry + l1NextVal + l2NextVal;
                var nextVal = nextSum % 10;

                result.next = new ListNode(nextVal);

                var needCarry_2 = nextSum >= 10;
                var hasL1Next_2 = hasL1Next && l1.next.next != null;
                var hasL2Next_2 = hasL2Next && l2.next.next != null;

                if (needCarry_2 || hasL1Next_2 || hasL2Next_2)
                {
                    var carry_2 = needCarry_2 ? 1 : 0;
                    var l1Next_2_Val = l1.next?.next?.val ?? 0;
                    var l2Next_2_Val = l2.next?.next?.val ?? 0;
                    result.next.next = new ListNode(carry_2 + l1Next_2_Val + l2Next_2_Val);
                }
            }

            return result;
        }

Step 21, 重構(gòu)：以遞迴取代原本的 next 與 next.next 的處理

生產(chǎn)代碼如下：

    public class Solution
    {
        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            return CreateSumNode(l1, l2, 0);
        }

        private ListNode CreateSumNode(ListNode l1, ListNode l2, int carry)
        {
            if (l1 == null && l2 == null)
            {
                if (carry == 0)
                {
                    return null;
                }

                return new ListNode(carry);
            }

            var l1Val = l1?.val ?? 0;
            var l2Val = l2?.val ?? 0;

            var rootSum = carry + l1Val + l2Val;
            var rootVal = rootSum % 10;

            var result = new ListNode(rootVal);

            var carryNext = rootSum >= 10 ? 1 : 0;
            result.next = CreateSumNode(l1?.next ?? null, l2?.next ?? null, carryNext);

            return result;
        }
    }

第一次進(jìn)位值以 0 帶入。判斷傳入的 L1, L2 若為 null 則終止遞迴菱父。

Step 22, 重構(gòu)：清理颈娜，得到最終版本生產(chǎn)代碼

最終版本生產(chǎn)代碼：

    public class Solution
    {
        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            return CreateSumNode(l1, l2, 0);
        }

        private ListNode CreateSumNode(ListNode l1, ListNode l2, int carry)
        {
            if (l1 == null && l2 == null)
            {
                return carry == 0 ? null : new ListNode(carry);
            }

            var nodeSum = NodeSum(l1, l2, carry);

            var result = new ListNode(nodeSum % 10);

            var carryToHigherDigit = nodeSum >= 10 ? 1 : 0;
            result.next = CreateSumNode(l1?.next ?? null, l2?.next ?? null, carryToHigherDigit);

            return result;
        }

        private static int NodeSum(ListNode l1, ListNode l2, int carry)
        {
            var l1Val = l1?.val ?? 0;
            var l2Val = l2?.val ?? 0;

            var nodeSum = carry + l1Val + l2Val;
            return nodeSum;
        }
    }

通過(guò) LeetCode 所有測(cè)試案例

通過(guò) LeetCode 所有測(cè)試案例

結(jié)論

如前言所說(shuō)，再次強(qiáng)調(diào)：

1. 測(cè)試程式的重構(gòu)浙宜，有助於提昇 TDD 撰寫(xiě)測(cè)試案例的速度官辽，並凸顯測(cè)試案例的關(guān)鍵代表性
2. 設(shè)計(jì)測(cè)試案例的順序，有助降低於 TDD baby step 化繁為簡(jiǎn)粟瞬，用最小步伐堆砌生產(chǎn)代碼的進(jìn)入門(mén)檻同仆。而 baby step 品質(zhì)的好壞，會(huì)影響重構(gòu)的成本與範(fàn)圍裙品。
3. baby step + 及時(shí)重構(gòu)俗批，可以讓重構(gòu)的難度、成本市怎、範(fàn)圍岁忘，降到最低。重構(gòu)時(shí)使用一些手法輔助区匠，則可以凸顯出重複的代碼邏輯干像，有利於淬取抽象或共用的方法。

Reference

兩個(gè)版本的 github commit history

1. 不夠好的測(cè)試案例順序
2. 本文的測(cè)試案例順序

社群交流回饋

• @武可 提到各段落步驟可加上 step 編號(hào)，以利社群交流討論
• @張?jiān)评?/strong> 提到 hasL1Next 的命名麻汰，太過(guò)於針對(duì)實(shí)作細(xì)節(jié)的速客，應(yīng)給予業(yè)務(wù)意義。因?yàn)檫@個(gè)使用情境就是兩大數(shù)相加什乙，所以可以將這個(gè)變數(shù)抽成方法：bool hasHigherDigits(ListNode<int> list)
• carryNext 改成 carryToHigherDigit
• @武可 提到挽封，step 10, 12 那兩個(gè) hard-code 的 else if block，到 step 13 的重構(gòu)臣镣，看起來(lái)代碼異動(dòng)比較大辅愿，而且不是被測(cè)試案例驅(qū)動(dòng)的。