# Add Two Numbers

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* head = NULL;
    struct ListNode* current = NULL;
    int carry = 0;
    
    while(l1 != NULL || l2 != NULL || carry != 0) {
        int sum = carry;
        
        if(l1) {
            sum += l1->val;
            l1 = l1->next;
        }
        if(l2) {
            sum += l2->val;
            l2 = l2->next;
        }
        
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = sum % 10;
        newNode->next = NULL;
        
        
        if(!head) {
            head = current = newNode;
        } else {
            current->next = newNode;
            current = newNode;
        }
        
        carry = sum / 10;
    }
    
    return head;
}

### ==**interviewer**==：
Welcome Tim! nice to meet you!
I've already sent you a goole doc link.
please make sure you can open it!

### **interviewee**：
I can open it!

### ==**interviewer**==：
great! then let's get started on our interview!
The question you will have to solve later is called "Add Two Numbers."

The situation is that:

We have two linked lists. Each node is one digit. Digits are in reverse order. You need to add the two numbers and return a new list, also in reverse order. You must handle different lengths and a possible final carry.

Feel free to ask me any question!

### **interviewee**：
Is all the digit between 0-9?

### ==**interviewer**==：
yes! you're right!

### **interviewee**：
No problem! But before I start to code it up, can I give a simple example, to check whether the way I'm thinking now is right?

### ==**interviewer**==：
Sure! Go ahead!

### **interviewee**：
342 + 465 → 2→4→3 + 5→6→4 → 7→0→8 (807)

Is that correct?

### ==**interviewer**==：
yeah! good job! Then what will be your approach to this question?

### **interviewee**：
My plan is simple. I will use a loop. In each step, I add digits from both lists plus the carry. then i'll create a new node in every loop. The carry is saved for the next step. This rule repeats until both lists and the carry are finished.

### ==**interviewer**==：
Hmmm… Sounds good!
Please show me your code. And explain to me while your are writing down every step.

### **interviewee**：
No problem!

First, I define the linked-list node type. Each node stores one digit and a pointer to the next node.

//Definition for singly-linked list.
struct ListNode {
     int val;
     struct ListNode *next;
 };

Next, I define the function. It receives the heads of l1 and l2, and it will return the head of the summed result list.

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* head = NULL;
    struct ListNode* current = NULL;
    int carry = 0;

Now I enter a loop. It continues as long as either list still has digits, or there is a non-zero carry.

    while (l1 != NULL || l2 != NULL || carry != 0) {

For each step, I start the sum with the incoming carry so the previous overflow is always included.

        int sum = carry;

If l1 exists, I add its digit into sum and move l1 to the next node.

        if (l1) {
            sum += l1->val;
            l1 = l1->next;
        }    

same for l2

        if (l2) {
            sum += l2->val;
            l2 = l2->next;
        }

Now sum represents digit1 + digit2 + carry. I create a new node for the result digit: I store sum % 10, and set next to NULL

        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = sum % 10;
        newNode->next = NULL;

If this is the first node, I initialize both head and current. Otherwise, I append the new node to the tail and move current forward. This builds the result list in correct order from least significant digit to most.

        if (!head) {
            head = current = newNode;
        } else {
            current->next = newNode;
            current = newNode;
        }

Finally,update carry using integer division: sum / 10. The carry will be 0 or 1.

        carry = sum / 10;
    }

When the loop ends, both lists are fully consumed and the carry is zero, so I return head as the start of the final summed list.

    return head;
}

So, that's is!

### ==**interviewer**==：
nice job! so why is the loop condition `l1 || l2 || carry`? What would happen if you removed carry?

### **interviewee**：
I include carry to ensure we don’t miss a final carry after both lists are exhausted. If I removed carry, cases like 9 + 1 would fail: after creating the first result node with value 0, both l1 and l2 become NULL, but carry is still 1. Without checking carry in the loop condition, the loop would stop and the result would incorrectly be just 0 instead of 0 -> 1.

### ==**interviewer(Follow-up)**==：
I see! And What if the digits in the linked lists are stored in forward order (most significant digit first)?
For example, 342 is 3 -> 4 -> 2 and 465 is 4 -> 6 -> 5.
You still need to return the sum as a linked list in forward order.
How would you solve it without converting to integers?

### **interviewee**：
If digits are in forward order, we can’t add from the head directly because carry propagates from the tail backward.

I will use two stacks (stack1 and stack2)
Push all digits of l1 into stack1, push digits of l2 into stack2.Pop from both stacks to simulate adding from the least significant digit.Each time we compute sum = x + y + carry, create a new node with sum % 10.Insert the new node to the front of the result list (head insertion), because we’re building digits from low to high but need forward order.Continue until both stacks are empty and carry is 0.

while (!is_empty(&s1) || !is_empty(&s2) || carry != 0) {
        int x = is_empty(&s1) ? 0 : pop(&s1);
        int y = is_empty(&s2) ? 0 : pop(&s2);

        int sum = x + y + carry;
        carry = sum / 10;

        struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = sum % 10;

        node->next = head;
        head = node;
    }

### ==**interviewer**==：
Nice explanation，thanks for your participation today! I really look forward to work with you in the future!

have a nice day!

### **interviewee**：
Thank you! 88!