Add Two Numbers - C Solution

1. Introduction

In this post, we address a classic problem in linked list manipulation, known as "Add Two Numbers". The challenge involves adding two non-negative integers represented by two linked lists, where each node contains a single digit of the number in reverse order. This problem is a great example of linked list traversal and manipulation in C programming.

Problem

Given two non-empty linked lists representing two non-negative integers, where digits are stored in reverse order, and each node contains a single digit, the task is to add the two numbers and return the sum as a linked list. The numbers do not contain any leading zero, except the number 0 itself.

2. Solution Steps

1. Initialize a new linked list to store the result.

2. Traverse both linked lists simultaneously, adding corresponding digits.

3. Keep track of the carry from each addition.

4. Handle different lengths of input lists and the carry at the end.

5. Return the head of the resulting linked list.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

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

// Function to add two numbers represented by linked lists
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* result = NULL;
    struct ListNode** node = &result;
    int carry = 0;

    while (l1 != NULL || l2 != NULL || carry) {
        int sum = carry;
        if (l1 != NULL) {
            sum += l1->val;
            l1 = l1->next;
        }
        if (l2 != NULL) {
            sum += l2->val;
            l2 = l2->next;
        }
        carry = sum / 10;

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

    return result;
}

// Helper function to create a new ListNode
struct ListNode* newNode(int val) {
    struct ListNode* node = (struct ListNode*) malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// Main function to test the addTwoNumbers function
int main() {
    // Example: (2 -> 4 -> 3) + (5 -> 6 -> 4)
    struct ListNode* l1 = newNode(2);
    l1->next = newNode(4);
    l1->next->next = newNode(3);

    struct ListNode* l2 = newNode(5);
    l2->next = newNode(6);
    l2->next->next = newNode(4);

    struct ListNode* result = addTwoNumbers(l1, l2);

    // Print the result
    printf("Sum: ");
    while (result != NULL) {
        printf("%d ", result->val);
        struct ListNode* temp = result;
        result = result->next;
        free(temp);
    }

    // Free the input lists
    free(l1->next->next);
    free(l1->next);
    free(l1);
    free(l2->next->next);
    free(l2->next);
    free(l2);

    return 0;
}

Output:

Sum: 7 0 8

Explanation:

1. addTwoNumbers traverses the two input linked lists, adding digits and handling the carry.

2. A new linked list is dynamically created to store the sum.

3. The main function demonstrates the functionality with an example, prints the resulting linked list, and frees the allocated memory.