Solving the ‘Add Two Numbers’ Problem on LeetCode — C Solutions Walkthrough (2024)

Table of Contents
Function Signature in C: Example 1: Example 2: Example 3: Constraints C Code: Time and Space Complexity C Code: Time and Space Complexity C Code: Time and Space Complexity Solution 1: Iterative Approach with Carry Handling Solution 2: Recursive Approach Solution 3: Optimized Iterative Approach with Node Reuse Summary Solution 1: Iterative Approach with Carry Handling Solution 2: Recursive Approach Solution 3: Optimized Iterative Approach with Node Reuse References
Solving the ‘Add Two Numbers’ Problem on LeetCode — C Solutions Walkthrough (2)

The ‘Add Two Numbers’ problem on LeetCode involves adding two non-empty linked lists representing two non-negative integers. Each list’s 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.

C is a powerful language well-suited for handling low-level memory management, which is beneficial when dealing with linked lists. This article provides a detailed walkthrough of three distinct C solutions to tackle the ‘Add Two Numbers’ problem. By the end of this guide, you will understand the mechanics behind each approach and their efficiency and effectiveness. Code comments and detailed step-by-step explanations for each method are provided after the conclusion.

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

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.

See Also
Merge Two Sorted Lists - Leetcode Solution - CodingBroz

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Function Signature in C:

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

Example 1:

Solving the ‘Add Two Numbers’ Problem on LeetCode — C Solutions Walkthrough (3)
  • Input: l1 = [2,4,3], l2 = [5,6,4]
  • Output: [7,0,8]
  • Explanation: 342 + 465 = 807.

Example 2:

  • Input: l1 = [0], l2 = [0]
  • Output: [0]

Example 3:

  • Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  • Output: [8,9,9,9,0,0,0,1]

Constraints

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

This simple approach involves iterating through both linked lists, summing corresponding digits, and managing the carry for sums greater than 9.

C Code:

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
 struct ListNode dummy;
 struct ListNode* current = &dummy;
 int carry = 0;
 dummy.next = NULL;
 while (l1 != NULL || l2 != NULL) {
 int x = (l1 != NULL) ? l1->val : 0;
 int y = (l2 != NULL) ? l2->val : 0;
 int sum = carry + x + y;
 carry = sum / 10;
 current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
 current->next->val = sum % 10;
 current->next->next = NULL;
 current = current->next;
 if (l1 != NULL) l1 = l1->next;
 if (l2 != NULL) l2 = l2->next;
 }
 if (carry > 0) {
 current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
 current->next->val = carry;
 current->next->next = NULL;
 }
 return dummy.next;
}

Time and Space Complexity

  • Time Complexity: O(n), the algorithm traverses both linked lists l1 and l2 exactly once. In each iteration, it processes one node from each list and performs a constant amount of work (addition, carry handling, and node creation). Therefore, the time complexity is linear relative to the length of the longer list.
  • Space Complexity: O(n), the space complexity is determined by the space required to store the result linked list. Since a new node is created for each digit of the sum, the space complexity is proportional to the length of the resulting list, which is O(n). The auxiliary space used for variables such as carry, dummy, and current is constant (O(1)), but the new linked list accounts for the overall O(n) space complexity.

This approach uses recursion to handle the addition of digits and carry, simplifying the iterative logic by breaking it down into smaller recursive calls.

C Code:

struct ListNode* addTwoNumbersHelper(struct ListNode* l1, struct ListNode* l2, int carry) {
 if (l1 == NULL && l2 == NULL && carry == 0) {
 return NULL;
 }
 int sum = carry;
 if (l1 != NULL) {
 sum += l1->val;
 l1 = l1->next;
 }
 if (l2 != NULL) {
 sum += l2->val;
 l2 = l2->next;
 }
 struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
 newNode->val = sum % 10;
 newNode->next = addTwoNumbersHelper(l1, l2, sum / 10);
 return newNode;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
 return addTwoNumbersHelper(l1, l2, 0);
}

Time and Space Complexity

  • Time Complexity: O(n), similar to the iterative approach, the recursive solution processes each node of the input lists once. Each recursive call handles one digit addition and proceeds to the next nodes of l1 and l2, making the time complexity linear in relation to the length of the longer list.
  • Space Complexity: O(n), the space complexity includes both the space for the new linked list and the recursive call stack. Each recursive call consumes stack space, which leads to O(n) space complexity due to recursion depth being equal to the length of the longer list. Additionally, the new linked list created to store the result contributes to O(n) space complexity. Thus, the total space complexity is O(n) for both the call stack and the new linked list.

This approach optimizes space usage by pre-allocating nodes for the result linked list and reusing nodes from the input lists wherever possible.

C Code:

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
 struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
 struct ListNode* current = dummy;
 struct ListNode* nextNode;
 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;
 sum = sum % 10;
 nextNode = (struct ListNode*)malloc(sizeof(struct ListNode));
 nextNode->val = sum;
 nextNode->next = NULL;
 current->next = nextNode;
 current = nextNode;
 }
 struct ListNode* result = dummy->next;
 free(dummy);
 return result;
}

Time and Space Complexity

  • Time Complexity: O(n), the optimized iterative approach also processes each node of l1 and l2 exactly once. Each iteration involves constant-time operations, such as value extraction, sum computation, carry handling, and node reassignment. As a result, the time complexity is linear (O(n)) with respect to the length of the longer list.
  • Space Complexity: O(1), this approach optimizes space usage by reusing existing nodes from the input lists instead of creating new nodes. The only additional space required is for a few auxiliary variables (dummy, current, and carry), which do not depend on the input size. Consequently, the space complexity is constant (O(1)), making this approach more space-efficient compared to the other solutions.

On analysis, all three C methods have similar time complexities, as each involves a single traversal of the input linked lists. The space complexity varies across the solutions due to different strategies for handling the result linked list and carry.

Solution 1: Iterative Approach with Carry Handling

  • Pros: This approach is straightforward and easy to understand. It efficiently handles the addition of two numbers by iterating through the lists and managing the carry within a loop. The logic is clear and simple, making it easy to implement and debug.
  • Cons: It requires the creation of a new linked list to store the result, which results in a space complexity of O(n). This approach is less space-efficient compared to the optimized iterative solution.

Solution 2: Recursive Approach

  • Pros: The recursive approach provides an elegant and concise solution to the problem. It simplifies the iterative logic by breaking it down into smaller, manageable recursive calls. The code is clean and easy to follow, making it a good choice for those who prefer recursion.
  • Cons: The recursive approach has a higher space complexity due to the recursion stack, which can lead to O(n) space usage. This can be a limitation for very large input sizes, as it may cause stack overflow issues.

Solution 3: Optimized Iterative Approach with Node Reuse

  • Pros: This solution is the most space-efficient as it reuses existing nodes from the input lists wherever possible. By pre-allocating nodes and updating their values, it minimizes additional space usage, achieving a space complexity of O(1). This approach is ideal for handling large input sizes without excessive memory consumption.
  • Cons: The logic for node management is slightly more complex compared to the other solutions. It requires careful handling of node pointers and values, which can make the implementation more error-prone and harder to debug.

Summary

  • Solution 1: Iterative Approach with Carry Handling provides a balance between simplicity and efficiency, making it a good starting point for understanding the problem.
  • Solution 2: Recursive Approach offers a clean and elegant solution, but its higher space complexity can be a limitation for large inputs.
  • Solution 3: Optimized Iterative Approach with Node Reuse is the most space-efficient and suitable for large input sizes, though it requires careful implementation.

While the second solution offers elegance and the first is a straightforward approach, the third solution provides the best combination of efficiency and space optimization. The use of node reuse in Solution 3 reflects a practical approach to handling linked list operations, which is often preferred in software development for its memory efficiency and effectiveness.

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated and helps keep content like this free!

Also check out my other Leetcode Walkthrough Lists:

  • Two Sum Problem
  • Palindrome Number Problem

Solution 1: Iterative Approach with Carry Handling

In this approach, we use an iterative method to traverse the input linked lists. We maintain a running sum of the digits and handle the carry for sums greater than 9. This solution iterates through both linked lists, adding corresponding digits along with any carry from the previous step. If the sum of the digits exceeds 9, the carry is updated accordingly. A new linked list is created to store the result, with each node representing a digit of the sum. This method makes sure that all digits are processed correctly, including the final carry if it exists.

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
 // Create a dummy node to serve as the head of the result list
 struct ListNode dummy;
 struct ListNode* current = &dummy;
 int carry = 0;
 // Initialize the next pointer of the dummy node to NULL
 dummy.next = NULL;
 // Loop until both linked lists are fully traversed
 while (l1 != NULL || l2 != NULL) {
 // Get the values of the current nodes or 0 if the node is NULL
 int x = (l1 != NULL) ? l1->val : 0;
 int y = (l2 != NULL) ? l2->val : 0;
 int sum = carry + x + y; // Calculate the sum including the carry
 carry = sum / 10; // Update the carry
 // Create a new node for the current digit and link it to the result list
 current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
 current->next->val = sum % 10;
 current->next->next = NULL;
 current = current->next; // Move to the next node
 // Move to the next nodes in the input lists
 if (l1 != NULL) l1 = l1->next;
 if (l2 != NULL) l2 = l2->next;
 }
 // If there's a remaining carry, add a new node for it
 if (carry > 0) {
 current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
 current->next->val = carry;
 current->next->next = NULL;
 }
 return dummy.next; // Return the head of the result list
}

Step-by-Step Explanation

  • Step 1: Initialize a dummy node to serve as the head of the result list and a current pointer to build the result list. Initialize carry to 0.
  • Step 2: Traverse l1 and l2 simultaneously.
  • Step 3: Extract the values of the current nodes (x and y). If a list has been fully traversed, use 0 as the value.
  • Step 4: Compute the sum of the current values and the carry.
  • Step 5: Determine the new carry by dividing the sum by 10.
  • Step 6: Create a new node with the value of sum % 10 and link it to the result list.
  • Step 7: Move the current pointer to the new node.
  • Step 8: Move to the next nodes in l1 and l2.
  • Step 9: After exiting the loop, check if there is any remaining carry. If so, create a new node with the carry value and link it to the result list.
  • Step 10: Return the next of the dummy node as the head of the result list.

Solution 2: Recursive Approach

This approach uses recursion to handle the addition of digits and carry, simplifying the iterative logic by breaking it down into smaller recursive calls. At each step, the function processes one digit from each input list, adds them along with the carry, and recursively proceeds to the next nodes. The base case for the recursion handles the situation where both input lists are null and no carry remains. This method leverages the call stack to manage the state, which can make the code more elegant and concise, especially for those who prefer a recursive solution.

struct ListNode* addTwoNumbersHelper(struct ListNode* l1, struct ListNode* l2, int carry) {
 if (l1 == NULL && l2 == NULL && carry == 0) {
 return NULL; // Base case: if all are null and no carry, return null
 }
 int sum = carry;
 if (l1 != NULL) {
 sum += l1->val; // Add value from l1 if not null
 l1 = l1->next; // Move to the next node in l1
 }
 if (l2 != NULL) {
 sum += l2->val; // Add value from l2 if not null
 l2 = l2->next; // Move to the next node in l2
 }
 // Create a new node for the current digit
 struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
 newNode->val = sum % 10;
 // Recursive call with next nodes and updated carry
 newNode->next = addTwoNumbersHelper(l1, l2, sum / 10);
 return newNode;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
 return addTwoNumbersHelper(l1, l2, 0); // Initial call with carry 0
}

Step-by-Step Explanation

  • Step 1: Base case: If both l1 and l2 are null and there is no carry, return NULL.
  • Step 2: Initialize sum with the carry.
  • Step 3: Add the value from l1 to sum if l1 is not null, then move to the next node in l1.
  • Step 4: Add the value from l2 to sum if l2 is not null, then move to the next node in l2.
  • Step 5: Create a new node with the value of sum % 10.
  • Step 6: Recursively call the helper function with the next nodes of l1 and l2, passing the new carry (sum / 10).
  • Step 7: Link the result of the recursive call to the next of the new node.
  • Step 8: Return the newly created node.

Solution 3: Optimized Iterative Approach with Node Reuse

This approach optimizes space usage by pre-allocating nodes for the result linked list and reusing nodes from the input lists wherever possible. Instead of creating new nodes for the result, this method updates and reuses the existing nodes from the input lists. This not only reduces the space complexity but also minimizes the overhead associated with dynamic memory allocation. By carefully managing node pointers and values, this solution achieves efficient memory usage while correctly handling the addition and carry operations.

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
 // Create a dummy node to serve as the starting point for the result list
 struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
 struct ListNode* current = dummy; // Pointer to build the result list
 struct ListNode* nextNode; // Pointer for pre-allocating nodes
 int carry = 0; // Initialize carry to 0
 // Loop until both linked lists are fully traversed and there is no carry left
 while (l1 != NULL || l2 != NULL || carry) {
 int sum = carry; // Start with the carry value
 // Add value from l1 if not null and move to the next node in l1
 if (l1 != NULL) {
 sum += l1->val;
 l1 = l1->next;
 }
 // Add value from l2 if not null and move to the next node in l2
 if (l2 != NULL) {
 sum += l2->val;
 l2 = l2->next;
 }
 carry = sum / 10; // Calculate the new carry
 sum = sum % 10; // Get the digit to store in the current node
 // Pre-allocate the next node
 nextNode = (struct ListNode*)malloc(sizeof(struct ListNode));
 nextNode->val = sum;
 nextNode->next = NULL;
 // Link the pre-allocated node to the current node
 current->next = nextNode;
 current = nextNode; // Move to the next node
 }
 struct ListNode* result = dummy->next; // The actual head of the result list
 free(dummy); // Free the dummy node
 return result; // Return the result list
}

Step-by-Step Explanation

  • Step 1: Initialize a dummy node to serve as the head of the result list and a current pointer to build the result list. Initialize carry to 0.
  • Step 2: Traverse l1 and l2 simultaneously.
  • Step 3: Extract the values of the current nodes (x and y). If a list has been fully traversed, use 0 as the value.
  • Step 4: Compute the sum of the current values and the carry.
  • Step 5: Determine the new carry by dividing the sum by 10.
  • Step 6: Pre-allocate a new node with the value of sum % 10.
  • Step 7: Link the pre-allocated node to the current node.
  • Step 8: Move the current pointer to the pre-allocated node.
  • Step 9: Move to the next nodes in l1 and l2.
  • Step 10: After exiting the loop, check if there is any remaining carry. If so, create a new node with the carry value and link it to the result list.
  • Step 11: Return the next of the dummy node as the head of the result list.
Solving the ‘Add Two Numbers’ Problem on LeetCode — C Solutions Walkthrough (2024)

References

Top Articles
Solving the Megaminx (Faster and Simpler)
St. Clair County Jail – Pell City , AL Inmate Search: Roster & Mugshots
Late Bloomers: The Hidden Strengths of Learning and Suc…
Mobipast
Top Posts Tagged with #yandere ramuda amemura x you | Tumlook
yandere - jxssq12 - Wattpad
The Applied Math Major at Ohio State University - Main Campus
Undergraduate Major in Statistics | Department of Statistics
Alanna Ubach | Rotten Tomatoes
Alanna Ubach on Suze’s ‘Euphoria’ Journey
Lowes 3238
Rylo Rodriguez Arrested
Latest Posts
The Megaminx - How To Solve It With The Beginner's Method
Learn how to solve Megaminx for beginners
Article information

Author: Errol Quitzon

Last Updated:

Views: 5742

Rating: 4.9 / 5 (59 voted)

Reviews: 90% of readers found this page helpful

Author information

Name: Errol Quitzon

Birthday: 1993-04-02

Address: 70604 Haley Lane, Port Weldonside, TN 99233-0942

Phone: +9665282866296

Job: Product Retail Agent

Hobby: Computer programming, Horseback riding, Hooping, Dance, Ice skating, Backpacking, Rafting

Introduction: My name is Errol Quitzon, I am a fair, cute, fancy, clean, attractive, sparkling, kind person who loves writing and wants to share my knowledge and understanding with you.