Add Two Numbers Represented by Linked Lists in C

This program demonstrates how to add two numbers represented by two linked lists. Each node in the linked list contains a single digit of the number, and the digits are stored in reverse order, meaning the 1’s place is at the head of the list.

Program Explanation

The program defines a linked list node structure and includes functions to insert nodes, add two linked lists that represent numbers, and display the results. The addition is performed similarly to how you would add two numbers digit by digit, carrying over any extra value if necessary.

• struct Node: Defines the structure of a linked list node with an integer data field and a pointer to the next node.
• insertNode: Inserts a new node at the head of the linked list to represent digits in reverse order.
• addTwoLists: Adds two linked lists digit by digit, handling carry as needed.
• printList: Prints the digits of the linked list, representing the final sum of the two numbers.

Source Code

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

// Node structure for linked list
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node and insert at the head
void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// Function to add two numbers represented by linked lists
struct Node* addTwoLists(struct Node* first, struct Node* second) {
    struct Node* result = NULL;  // Store the result list
    struct Node *temp, *prev = NULL;
    int carry = 0, sum;

    // Traverse both lists
    while (first != NULL || second != NULL) {
        // Calculate the sum of corresponding nodes' data + carry
        sum = carry + (first ? first->data : 0) + (second ? second->data : 0);

        // Update carry for next calculation
        carry = (sum >= 10) ? 1 : 0;
        sum = sum % 10;

        // Create a new node for the sum and add it to the result list
        temp = (struct Node*) malloc(sizeof(struct Node));
        temp->data = sum;
        temp->next = NULL;

        if (result == NULL) {
            result = temp;
        } else {
            prev->next = temp;
        }
        prev = temp;

        // Move first and second pointers to the next nodes
        if (first) first = first->next;
        if (second) second = second->next;
    }

    // If carry is still left after the final digit, add a new node
    if (carry > 0) {
        temp = (struct Node*) malloc(sizeof(struct Node));
        temp->data = carry;
        temp->next = NULL;
        prev->next = temp;
    }

    return result;
}

// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\\n");
}

int main() {
    struct Node* first = NULL;
    struct Node* second = NULL;
    struct Node* result = NULL;

    // Create first list: 243 (3 -> 4 -> 2)
    insertNode(&first, 3);
    insertNode(&first, 4);
    insertNode(&first, 2);
    printf("First number: ");
    printList(first);

    // Create second list: 564 (4 -> 6 -> 5)
    insertNode(&second, 4);
    insertNode(&second, 6);
    insertNode(&second, 5);
    printf("Second number: ");
    printList(second);

    // Add the two lists
    result = addTwoLists(first, second);
    printf("Resultant sum: ");
    printList(result);

    return 0;
}
        

Explanation of the Program Structure:

1. Node Structure (struct Node): This structure defines a linked list node that holds an integer (data) and a pointer to the next node (next).
2. insertNode() Function: Inserts a new node with the given data at the head of the linked list. This is used to build the linked list representing the number in reverse order (for example, 243 is stored as 3 -> 4 -> 2).
3. addTwoLists() Function: Adds two numbers represented by linked lists. It traverses both lists, adds corresponding digits, and handles carry-over. If a carry remains after processing all nodes, an additional node is added at the end.
4. printList() Function: Prints the digits of the linked list to display the numbers and the final result.

How the Program Works:

• The program constructs two linked lists to represent two numbers, adds them, and stores the result in a new linked list.
• For example, the linked lists representing 243 (3 -> 4 -> 2) and 564 (4 -> 6 -> 5) are added together to form the result 807 (7 -> 0 -> 8).

Conclusion

This C program effectively adds two numbers represented by linked lists, handling each digit from the least significant to the most significant (reverse order) and managing carry-over as needed. The result is stored in another linked list representing the sum of the two numbers.