Adding two integers represented by linked lists

Question

The question I came across.

Here is what I have done so far

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

struct node
{
  int digit;
  struct node *next;
};

struct node *make_node(int num, struct node *head);
struct node *newNode(int digit);
struct node *sum(struct node *num1, struct node *num2);
void print(struct node *node);

int main()
{

  int a, b;
  struct node *new_nodeA1 = NULL, *new_nodeA2 = NULL;
  struct node *new_nodeB1 = NULL, *new_nodeB2 = NULL;
  struct node *res = NULL;

  printf("\nEnter no. of digits for your two numbers (separate with space)  ");
  scanf("%d %d", &a, &b);
  int n1[a], n2[b];

  printf("\n\nEnter first non-negative integer to add:  ");
  for (int j = 0; j < a; j++)
    scanf("%1d", &n1[j]);
  printf("Enter second non-negative integer to add:  ");
  for (int k = 0; k < b; k++)
    scanf("%1d", &n2[k]);

  /* for (int i = 0; i <= a - 1; i++)
    printf("%d\n", n1[i]);

    printf("%d\n", a); */

  for (int z = 0; z < a - 1; z++)
    {
      new_nodeA2 = make_node(n1[z], new_nodeA1);
      /*new_nodeA2 = newNode(n1[z]);*/
      if (new_nodeA1 == NULL)
    new_nodeA1 = new_nodeA2;
    }

  for (int y = 0; y < b - 1; y++)
    {
      new_nodeB2 = make_node(n2[y], new_nodeB1);
      if (new_nodeB1 == NULL)
    new_nodeB1 = new_nodeB2;
    }

  printf("\n");
  print(new_nodeA1);
  printf("\n");
  print(new_nodeB1);
  printf("\n")
  res = sum(new_nodeA2, new_nodeB2);
  printf("Result: ");
  print(res);
  return 0;

}

struct node *make_node(int num, struct node *head)
{

  struct node *temp = malloc(sizeof(struct node));

  if (temp == NULL)
    {
      fprintf(stderr, "Call of malloc() failed\n");
      exit(1);
    }

  if (head != NULL)
    head->next = temp;

  temp->digit = num;
  temp->next = NULL;

  return temp;

}

struct node *newNode(int digit)
{
    struct node *new_node = (struct node *) malloc(sizeof(struct node));
    new_node->digit = digit;
    new_node->next = NULL;
    return new_node;
}

struct node *sum(struct node *num1, struct node *num2)
{
    struct node *res = NULL;
    struct node *temp, *prev = NULL;
    int carry = 0, sum;

    while (num1 != NULL || num2 != NULL)
    {
        sum = carry + (num1? num1->digit: 0) + (num2? num2->digit: 0);
        carry = (sum >= 10)? 1 : 0;
        sum = sum % 10;


        temp = newNode(sum);


        if(res == NULL)
            res = temp;
        else
            prev->next = temp;

        prev  = temp;

        if (num1) 
      num1 = num1->next;
        if (num2) 
      num2 = num2->next;
    }

    if (carry > 0)
      temp->next = newNode(carry);

    return res;
}

void print(struct node *node)
{
    while(node != NULL)
    {
        printf("%d->", node->digit);
        node = node->next;
    }
    printf("\n");
}

My Output

My compiler does not give me any error. I tried debugging my make_node function but I cant catch the problem as to why my nodes are skipping certain digits.

Answer 1

Your linked list insert code is very broken. For this style of list, you need to walk down the list from head->next until a null is found and insert there. Instead, you are always replacing the head->next with your new temp node, thus breaking the list.

You can also add to the list backwards, making the newly added item the head each time and thus get around the traversal for add, but beware this will place your numbers in reverse order (which actually helps when you do your adding, so perhaps this is good too.)