No. 40 - Add on Lists

Problem: Nodes in a list represent a number. For example, the nodes in Figure 1 (a) and (b) represent numbers 123 and 4567 respectively. Please implement a function/method to add numbers in two lists, and store the sum into a new list.

Figure 1: Two lists representing numbers. (a) A list for 123; (b) A list for 4567.

Analysis: Usually numbers are added beginning from the least significant digits (The digit 3 in the number 123, and the digit 7 in the number 4567). As shown in Figure 1, the least significant digits are at the tail of lists, and they can be accessed after the whole lists are scanned. Therefore, lists should be reversed at first, in order get the least significant digits before other digits. The two reversed lists of lists in Figure 1 are shown in Figure 2.

Figure 2: Two reversed lists of the lists in Figure 1.

After two lists are reversed, we can add nodes along the links between nodes, and then reversed the result list after all nodes are added. Therefore, the overall structure to add numbers in two lists can be implemented with the following code in C/C++:

ListNode* Add(ListNode* pHead1, ListNode* pHead2)

{

    if(pHead1 == NULL || pHead2 == NULL)

        return NULL;

    pHead1 = Reverse(pHead1);

    pHead2 = Reverse(pHead2);

    ListNode* pResult = AddReversed(pHead1, pHead2);

    return Reverse(pResult);

}

Now let’s implement the function AddReversed, to add nodes in two reversed lists. Digits are gotten in nodes along links between nodes. When we get two digits in two lists, we add them and create a new node to store the sum, and append the new node into the list for result. There are two issues worthy of attention: (1) The length of two lists might be different; (2) The sum of two digits may be greater than 10, so we have to take care of the carry when adding two digits. The function AddReversed can be implemented with the following C/C++ code:

ListNode* AddReversed(ListNode* pHead1, ListNode* pHead2)

{

    int carry = 0;

    ListNode* pPrev = NULL;

    ListNode* pHead = NULL;

    while(pHead1 != NULL || pHead2 != NULL)

    {

        ListNode* pNode = AddNode(pHead1, pHead2, &carry);

        AppendNode(&pHead, &pPrev, pNode);

        if(pHead1 != NULL)

            pHead1 = pHead1->m_pNext;

        if(pHead2 != NULL)

            pHead2 = pHead2->m_pNext;

    }

    if(carry > 0)

    {

        ListNode* pNode = CreateListNode(carry);

        AppendNode(&pHead, &pPrev, pNode);

    }

    return pHead;

}

The function AddNode adds digits in two nodes. The third parameter of this function takes the carry for addition calculation, as listed below:

ListNode* AddNode(ListNode* pNode1, ListNode* pNode2, int* carry)

{

    int num1 = 0;

    if(pNode1 != NULL)

        num1 = pNode1->m_nValue;

    int num2 = 0;

    if(pNode2 != NULL)

        num2 = pNode2->m_nValue;

    int sum = num1 + num2 + *carry;

    *carry = (sum >= 10) ? 1 : 0;

    int value = (sum >= 10) ? (sum - 10) : sum;

    return CreateListNode(value);

}

The function AppendNode is used append a node into the tail of lists. In order to avoid scanning the whole list to get the previous tail every time, the previous tails is stored in the parameter/variable pPrev, as listed in the following code:

void AppendNode(ListNode** pHead, ListNode** pPrev, ListNode* pNode)

{

    if(*pHead == NULL)

        *pHead = pNode;

    if(*pPrev == NULL)

        *pPrev = pNode;

    else

    {

        (*pPrev)->m_pNext = pNode;

        *pPrev = pNode;

    }

}

The function CreateListNode is to create a list node according to a value, which is omitted here because it’s quite straightforward. 

The steps to reverse a list are discussed in my previous blog.

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.