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. 

No. 18 - Reverse a Linked List

Problem: Implement a function to reverse a linked list, and return the head of the reversed list. A list node is defined as below:

struct ListNode

{

       int       m_nKey;

       ListNode* m_pNext;

};

Analysis: Lots of pointer operations are necessary to solve problems related to linked lists. Interviewers know that many candidates are prone to make mistakes on pointer operations, so they like problems of linked list to qualify candidates’ programming abilities. During interviews, we had better analyze and design carefully rather than begin to code hastily. It is much better to write robust code with comprehensive analysis than write code quickly with many errors.

Direction of pointers should be adjusted in order to reverse a linked list. We may utilize figures to analyze visually the complex steps to adjust pointers. As shown in the list in Figure 1-a, node h, i and j are three adjacent nodes. Let us assume pointers of all nodes prior to h have been reversed after some operations and all m_pNext point to their previous nodes. We are going to reverse the m_pNext pointer in node i. The status of list is shown in Figure 1-b.

Figure 1: A list is broken when we reverse m_pNext pointers. (a) A linked list. (b) A link between node i and j is broken when all m_pNext pointers of node prior to node i point to their previous nodes.

It is noticeable that m_pNext in node i points to its previous node h, the list is broken and we cannot visit the node j anymore. We should save the node j before the m_pNext pointer of node i is adjusted to prevent the list becoming broken.

When we adjust the pointer in node i, we need to access to node h since m_pNext of node i is adjusted to point to node h. Meanwhile, we also need to access to node j because it is necessary to save it otherwise the list will be broken. Therefore, three pointers should be declared in our code, which point to the current visited node, its previous node and its next node.

Lastly we should get the head node of the reversed list. Obviously head in the reversed list should be tail of the original list. Which pointer is tail? It should be a node whose m_pNext is NULL.

With comprehensive analysis above, we are ready to write code, which is shown below:

ListNode* ReverseList(ListNode* pHead)

{

    ListNode* pReversedHead = NULL;

    ListNode* pNode = pHead;

    ListNode* pPrev = NULL;

    while(pNode != NULL)

    {

        ListNode* pNext = pNode->m_pNext;

        if(pNext == NULL)

            pReversedHead = pNode;

        pNode->m_pNext = pPrev;

        pPrev = pNode;

        pNode = pNext;

    }

    return pReversedHead;

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. 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 me (zhedahht@gmail.com) . Thanks.

No. 10 - K-th Node from End

Problem: Get the K^th node from end of a linked list. It counts from 1 here, so the 1^st node from end is the tail of list. 

For instance, given a linked list with 6 nodes, whose value are 1, 2, 3, 4, 5, 6, its 3^rd node from end is the node with value 4.

A node in the list is defined as:

struct ListNode

{

    int       m_nValue;

    ListNode* m_pNext;

};

Analysis: In a list with n nodes, its k^th node from end should be the (n-k+1)^th node from its head. Therefore, if we know the number of nodes n in a list, we can get the required node with n-k+1 steps from its head. How to get the number n? It is easy if we scan the whole list from beginning to end.

The solution above needs to scan a list twice: We get the total number of nodes with the first scan, and reach the k^th node from end with the second scan. Unfortunately, interviewers usually expect a solution which only scans a list once.

We have a better solution to get the k^th node from end with two pointers. Firstly we move a pointer (denoted as P1) k-1 steps beginning from the head of a list. And then we move another pointer (denoted as P2) beginning from the head, and continue moving the P1 forward at same speed. Since the distance of these two pointers is always k-1, P2 reaches the k^th node from end when P1 reaches the tail of a list. It scans a list only once, and it is more efficient than the previous solution.

Figure 1: Get the 3^rd node from end of a list with 6 nodes

It simulates the process to get the 3^rd node from end of a list with 6 nodes in Figure 1. We firstly move P1 2 steps (2=3-1) to reach the 3^rd node (Figure 1-a). Then P2 points to the head of a list (Figure 1-b). We move two pointers at the same speed, when the P1 reaches the tail, what P2 points is the 3^rd node from end (Figure 1-c).

The sample code of the solutions with two pointers is shown below:

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)

{

    if(pListHead == NULL || k == 0)

        return NULL;

    ListNode *pAhead = pListHead;

    ListNode *pBehind = NULL;

    for(unsigned int i = 0; i < k - 1; ++ i)

    {

        if(pAhead->m_pNext != NULL)

            pAhead = pAhead->m_pNext;

        else

        {

            return NULL;

        }

    }

    pBehind = pListHead;

    while(pAhead->m_pNext != NULL)

    {

        pAhead = pAhead->m_pNext;

        pBehind = pBehind->m_pNext;

    }

    return pBehind;

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. 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 me (zhedahht@gmail.com) . Thanks.