Post
Ask Question

How To Traverse And Add New Nodes Into LinkedList with Leetcode's Add two number problem.

Introduction

This leetcode's problem is a favorite question of coding interviews. The data structure we are going to work with is Singly LinkedList. It's super fun. 

Note: We are not going to use the inbuilt LinkedList class of C# because that is a doubly linked list.

The problem

Before we start the code, we first need to understand the problem clearly and make an algorithm to work with. Once you have an algorithm then it doesn’t even matter which programming language you are using.

Let's see what information do we have to work with. 

Read the problem in detail from LeetCode: Add two numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

Example 1:
               2 -> 4 -> 3
               5 -> 6 -> 4 
Result:    7 -> 0 -> 8
Explanation:  342 + 465 = 807, return 708

Example 2: 
              1 -> 2 -> 3
              1 -> 2  
Result:   2 -> 4 -> 3
Explanation:  321 + 021 = 342, return 243

Example 3:
              5 -> 6 -> 7
              5 -> 6 -> 7
Result:   0 -> 3 -> 5 -> 1
Explanation:  765 + 765 = 1530, return 0351

Note: These are non-empty lists so we don't need to add validations for empty lists.

Approach

Okay, so the problem says we need to reverse both lists to perform addition and then reverse the result. It may look complicated on the surface but it's really easy under the hood.

Technically we don't have to reverse anything. Since the last element in the example is the first element in the list. Neither we need to append zeros at empty spaces; instead, we can just skip that addition if the value of the node is null, as simple as that.

Algorithm (Follow example 3)

We need variables one to hold the sum, and the sum could be > 10 we need variables to hold carry and another to hold the remainder.

  • The looping (While loop): We iterate through the list until we reach the last node of the either list.
  • Iteration 1
    • With every iteration we are going to shrink the lists by one element.
    • With every shrinking loop there will be pointers CurrentNodeList1, CurrentNodeList2 which are the current nodes.
    • Now we need to add CurrentNodeList1.value + CurrentNodeList2.Value and update the variable sum.
      • Here is the condition: if the value of sum is > 10 then we have to store the remainder in newNode's value and division in carry, then add the newNode into the resultant linkedlist.
    • Let's understand this. In above example we have 5 and 5 as our first nodes.
      • Perform the sum of the values of the first nodes of both linkedlist.
        • 5 + 5 = 10;
      • We need to store the remainder in a new node.
        • NewNode.Value = 10%10 = 0;
      • Now add the NewNode into the new linkedlist which you were supposed to return.
        • ResultantLinkList = 0 -> null;
      • Calculate the carry with division and store it in a variable
        • Carry = 10/10 = 1;
  • Iteration 2
    • Coming for the next iteration we have to be sure that we use the carry from the last iteration which is 1.
      • Carry = 1;
      • Perform the sum of the values of the second nodes of both linkedlist.
        • 6 + 6 = 12
      • 6 + 6 = 12 but we also have to add the carry.
        • Sum = 1 + 6 + 6 = 13; 
      • We need to store the remainder in a new node.
        • NewNode.Value = 13%10 = 3;
      • Now add the NewNode into the new linkedlist which you were supposed to return.
        • ResultLinkList = 0-> 3 -> null;
      • Calculate the carry with division and store it in a variable
        • Carry = 13/10 = 1;
  • Iteration 3, Now you got the idea, So now I am going to skip the description.
    • Sum = 1 + 7 + 7 =15;
    • NewNode.Value = 15%10 = 5;
    • ResultLinkList = 0-> 3 -> 5-> null;
    • Carry = 15/10 = 1;
  • Last step
  • We are out of the while loop since we have no elements left in lists. But we still have that carry left from the last iteration. Now for this just add one more node to your resultant linkedlist with a carry.
    • ResultLinkList = 0-> 3 -> 5-> 1-> null;

Note: In first iteration we have to make sure we add new node as a head to the ResultantLinkedList and from next iteration it would be ResultantLinkList.next for next it would be ResultLinkList.next.next
As you can see we have a problem here. We are not going to add (.next) for every iteration.

Instead, we can use a temporary list to pass its reference to our resultant list, and then make temporary list points to current node. 

Let's bring this algorithm to life. Now please read all the comments to understand the logic.

  • class ListNode: As given by Leetcode 
    /// <summary>
/// Definition for singly - linked list.
/// </summary>
internal class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}
  • The logic\ Algorithm 
    internal class ListNodeAddition
{
    /// <summary>
    /// LeetCode have l1 and l2 as parameter's name, I am using currentNodeList1 to represent current node of list 1 
    /// currentNodeList2 to represent current node of list 2 
    /// </summary>
    /// <param name="currentNodeList1"></param>
    /// <param name="currentNodeList2"></param>
    /// <returns>List node of addition of list1 and list 2</returns>
    public ListNode AddTwoNumbers(ListNode currentNodeList1, ListNode currentNodeList2)
    {        
        // This is the list the method will return
        ListNode resultantList = null;

        // Reference of resultantList, we are going to use this to determine if resultant list's head node and managing it's next nodes
        ListNode resultantTempList = null;

        ListNode newNode = null;
        // carry to hold value if sum > 10
        int carry = 0;

        // 2 pointers as we mentioned in the algorithm
        while (currentNodeList1 != null || currentNodeList2 != null)
        {
            // next iteration might bring a carry with it, which we need to be added into the sum.
            int sum = carry;

            // Both lists don't necessarily have to be of same lengths, So if there is a node then we will add then we will simply skip.

            // current pointer of list 1 is not null, update the sum, and point current pointer to next node.
            if (currentNodeList1 != null)
            {
                sum += currentNodeList1.val;
                currentNodeList1 = currentNodeList1.next;
            }

            // current pointer of list 2 is not null, update the sum, and point current pointer to next node.
            if (currentNodeList2 != null)
            {
                sum += currentNodeList2.val;
                currentNodeList2 = currentNodeList2.next;
            }

            // we need to calculate the remainder and make a new link list node.
            // You don't necessarily need to create a variable to hold the value of remainder, this just makes code easy to read.
            int remainder = sum % 10;
            newNode = new(remainder);

            // As per our algorithm we need to take carry with us for the next iteration. result of division will give us the value of carry
            carry = sum / 10;


            // if this is the first node then set it as head
            if (resultantTempList == null)
            {
                resultantTempList = resultantList = newNode;
            }

            // If this is not the first node then adding node to the next
            else
            {
                // Adding next node of the temp list, And since it has been referenced by our resultant list
                // resultant list next element will automatically be updated. We are not referring resultant list anywhere
                // so current node is the last one, so for third iteration it will be next.next 
                resultantTempList.next = newNode;

                //Set temp list for next insertion
                resultantTempList = resultantTempList.next;
            }
        }
        // When there is no node left in either of the list to iterate but we have left with a carry from last iteration
        // We need to create a new node to store the value.
        if (carry > 0)
        {
            resultantTempList.next = new ListNode(carry);
        }

        // simply return the resultant list
        return resultantList;
    }
}
  • class program: to call the AddTwoNumbers() method with parameters. 
    public class Program
{
    static public void Main()
    {
        // creating first list
        ListNode l1 = new(2)
        {
            next = new ListNode(4)
            {
                next = new ListNode(3) { }
            }
        };
        //Printing list 1
        PrintListNode(l1);


        // creating second list
        ListNode l2 = new(5)
        {
            next = new ListNode(6)
            {
                next = new ListNode(4) { }
            }
        };
        //Printing list 2
        PrintListNode(l2);

        //Creating an instance of an class which contains the logic
        ListNodeAddition listNodeAddition = new();
        ListNode addedNodes = listNodeAddition.AddTwoNumbers(l1, l2);
        PrintListNode(addedNodes);
    }

    /// <summary>
    /// This method prints all the elements in the singly linked list
    /// </summary>
    /// <param name="head"></param>
    static void PrintListNode(ListNode head)
    {
        while (head != null)
        {
            Console.Write(head.val + " ");
            head = head.next;
        }
        Console.WriteLine();
    }
}

If you run the code and debug every step, you would be executing the following statements at runtime as shown in figure 1 and 2.

Note: input is 2 -> 4 -> 3 and 5 -> 6 -> 4. 

Figure 1

Figure 2

Now let’s see how code would debug for a second example.
Note: input is 1 -> 2 -> 3 and 1 -> 2

Figure 3

And that's how you do it.

Summary

Today, we learned how to create a singly linkedlist in C#, how to traverse through it. how to add new nodes into singly linkedlist and how to solve one of the most common questions of the technical interviews.

If you have any queries reach me @ Linkedin | Github


Similar Articles