Add Two Numbers

Problem Statement

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

 

Source: https://leetcode.com/problems/add-two-numbers/

Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space

 

Solution 

 

 

// List Node Structure 
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
    int carry = 0;
    // Create a dummy node as a start of new List
    ListNode newHead = new ListNode(0);
    // Pointers to respective list
    ListNode p1 = l1, p2 = l2, p3 = newHead;
    
    // While list 1 and list 2 are processed
    while (p1 != null || p2 != null)
    {
        if (p1 != null)
        {   
            
            carry += p1.val;
            p1 = p1.next;
        }

        if (p2 != null)
        {
            carry += p2.val;
            p2 = p2.next;
        }

        p3.next = new ListNode(carry % 10);
        p3 = p3.next;
        // If the result exceeds 10 keep track of carry
        carry /= 10;
    }
    
    // if carry is 1 create a new node 
    if (carry == 1)
        p3.next = new ListNode(1);

    // Return dummy nodes next 
    return newHead.next;
}