Leetcode第二題の詳細

Leetcode第二題の詳細
タイトルは以下の通りです.
Question
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8
この問題は相対的に簡単で、チェーンテーブルの最も基本的な操作を考察しています.唯一注意しなければならないのは、2つのチェーンテーブルの数が加算された後、キャリーがある場合は、キャリーを個別に処理する必要があります.

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
    ListNode * pCurrent, * pNext, * pHead = NULL;
    int carry  = 0;

    while(l1 || l2)
    {
        pNext = new ListNode(0);
        if(pHead == NULL)
        {
            pHead = pNext;
        }
        else
        {
            pCurrent->next = pNext;
        }
        pCurrent = pNext;

        int op1 = l1 ? l1->val : 0;
        int op2 = l2 ? l2->val : 0;
        int k = carry  + op1 + op2;

        carry  = k / 10;
        pCurrent->val = k % 10;

        if(l1) l1 = l1->next;
        if(l2) l2 = l2->next;
    }
    if(carry  != 0)
    {
        pNext = new ListNode(carry );
        pCurrent->next = pNext;
    }
    return pHead;
}

このコードは少し長いように見えます.主にチェーンテーブルのヘッダポインタは、チェーンテーブルの最初の要素を生成するときに単独で処理する必要があります.つまり、次のコードクリップです.

if(pHead == NULL)
{
    pHead = pNext;
}
else
{
    pCurrent->next = pNext;
}

いくつかの小さなテクニックを利用して、ここではもっと優雅に書くことができます.よく使われるテクニックは、チェーンテーブルの先頭に「哨兵」ノードを設定することです.このノードには具体的なデータは保存されません.このノードがあれば特殊な処理ヘッドポインタは必要ありません.この「哨兵」ノードがあれば、ヘッドポインタは必要ありません.次に、改良されたコードを示します.

ListNode* addTwoNumbers_2(ListNode* l1, ListNode* l2)
{
    ListNode headNode(0);
    ListNode *pCurrent = &headNode, *pNext;
    int carry  = 0;

    while(l1 || l2)
    {
        int op1 = l1 ? l1->val : 0;
        int op2 = l2 ? l2->val : 0;

        int k = carry  + op1 + op2;
        carry  = k / 10;
        pNext = new ListNode(k % 10);

        pCurrent->next = pNext;
        pCurrent = pNext;

        if(l1) l1 = l1->next;
        if(l2) l2 = l2->next;
    }
    if(carry  != 0)
    {
        pNext = new ListNode(carry );
        pCurrent->next = pNext;
    }
    return headNode.next;
}

これで、このコードは比較的簡潔に見えます.チェーンテーブルの先頭にこのような「歩哨」を付けることができるほか、チェーンテーブルの末尾に「歩哨」を付けることもコードを簡略化することができる.例えば、この問題では、終わりの哨兵を設定することができます.この哨兵の値は0で、nextポインタは自分を指します.この「哨兵」があれば、プログラムの間のwhileサイクルを簡素化することもできる.しかし、この哨兵を2つのチェーン時計の終わりに加えるのもオーバーヘッドだ.この例には、少し損をしているかもしれません.プレゼンテーションとして、コードを提示しました.実際のプロジェクトアプリケーションでは、この方法を使用する場合は、チェーンテーブルを作成するときに必ずこのエンドノードを追加します.

ListNode* addTwoNumbers_2(ListNode* l1, ListNode* l2)
{
    ListNode headNode(0);
    ListNode *pCurrent = &headNode, *pNext;

    ListNode tailNode(0);
    tailNode.next = &tailNode;

    pNext = l1;
    while(pNext->next) pNext = pNext->next;
    pNext->next = &tailNode;

    pNext = l2;
    while(pNext->next) pNext = pNext->next;
    pNext->next = &tailNode;

    int carry  = 0;

    while(l1 !=  &tailNode || l2 != &tailNode)
    {
        int k = carry  + l1->val + l2->val;
        carry  = k / 10;
        pNext = new ListNode(k % 10);

        l1 = l1->next;
        l2 = l2->next;
        pCurrent->next = pNext;
        pCurrent = pNext;

    }
    if(carry  != 0)
    {
        pNext = new ListNode(carry );
        pCurrent->next = pNext;
    }
    return headNode.next;
}