aboutsummaryrefslogtreecommitdiff
path: root/add_two_num2.c
blob: cdce99835436fff07a28817886c6e1bd52d8cdfe (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 445. Add Two Numbers II
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

/*
 * given two non-empty linked lists representing two non-negative integers. the
 * most significant digit comes first and each of their nodes contains a single
 * digit. add the two numbers and return the same as a linked list. you may
 * assume the two numbers do not contain any leading zero, except the number 0
 * itself.
 */

struct ListNode {
  int val;
  struct ListNode *next;
};

static int append(struct ListNode *l1, struct ListNode *l2, int missing) {
  int carry, val;
  if (!l1)
    return 0;
  if (!missing) {
    carry = append(l1->next, l2->next, 0);
    val = l1->val + l2->val + carry;
  } else {
    carry = append(l1->next, l2->next, -1);
    val = l1->val + carry;
  }
  l1->val = val % 10;
  return val / 10;
}

static int length(struct ListNode *n) {
  int len;
  for (len = 0; n; n = n->next)
    len++;
  return len;
}

static void swap(struct ListNode **p1, struct ListNode **p2) {
  struct ListNode *tmp;
  tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
  int len1, len2, carry;
  struct ListNode *head;
  len1 = length(l1);
  len2 = length(l2);
  if (len1 < len2)
    swap(&l1, &l2);
  carry = append(l1, l2, abs(len1 - len2));
  if (carry) {
    if (!(head = malloc(sizeof(struct ListNode))))
      return head;
    head->val = 1;
    head->next = l1;
  }
  return l1;
}