【LeetCode OJ】Add Two Numbers

  1 #include "stdafx.h"
  2 #include <malloc.h>
  3 #include <iostream>
  4 using namespace std;
  5 typedef struct ListNode {
  6     int val;
  7     ListNode *next;
  8     ListNode(int x) : val(x), next(NULL) {}
  9     
 10 }*Lnode;
 11 Lnode create()  //尾插法建立链表
 12 {
 13     Lnode head,q,r;
 14     int temp;
 15     head = (struct ListNode *)malloc(sizeof(Lnode));
 16     head->next = NULL;
 17     r = head;
 18     cin >> temp;
 19     while (temp!=-1)//输入-1，创建链表结束
 20     {
 21         q = (struct ListNode *)malloc(sizeof(Lnode));
 22         q->val = temp;
 23         r->next = q;
 24         r = q;
 25         cin >> temp;
 26     }
 27     r->next = NULL;
 28     return head;
 29 }
 30 void print(Lnode h)  //打印链表
 31 {
 32     Lnode p=h->next;
 33     while (p)
 34     {
 35         cout << p->val<<endl;
 36         p = p->next;
 37     }
 38 }
 39 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)     
 40 {
 41     int flag = 0;
 42     ListNode * p,*r;
 43     ListNode * h = (struct ListNode *)malloc(sizeof(ListNode *));
 44     h->next = NULL;
 45     r = h;
 46     int num;
 47     if (l1 == NULL) return l1;
 48     if (l2 == NULL) return l2;
 49     while (l1&&l2)
 50     {
 51             num = l1->val + l2->val + flag;
 52         if (num<10)
 53         {
 54             p = (struct ListNode *)malloc(sizeof(ListNode *));
 55             p->val = num;
 56             r->next = p;
 57             r = p;
 58             flag = 0;
 59         }
 60         else      //如果两位数相加大于10，则向前进一位
 61         {
 62             p = (struct ListNode *)malloc(sizeof(ListNode *));
 63             p->val = num-10;
 64             r->next = p;
 65             r = p;
 66             flag = 1;
 67         }
 68         l1 = l1->next;
 69         l2 = l2->next;
 70     }
 71     while (l1)  
 72     {
 73         num = l1->val + flag;
 74         if (num<10)
 75         {
 76             p = (struct ListNode *)malloc(sizeof(ListNode *));
 77             p->val = num;
 78             r->next = p;
 79             r = p;
 80             flag = 0;
 81         }
 82         else
 83         {
 84             p = (struct ListNode *)malloc(sizeof(ListNode *));
 85             p->val = num - 10;
 86             r->next = p;
 87             r = p;
 88             flag = 1;
 89         }
 90         l1 = l1->next;
 91 
 92     }
 93 
 94     while (l2)
 95     {
 96         num = l2->val + flag;
 97         if (num<10)
 98         {
 99             p = (struct ListNode *)malloc(sizeof(ListNode *));
100             p->val = num;
101             r->next = p;
102             r = p;
103             flag = 0;
104         }
105         else
106         {
107             p = (struct ListNode *)malloc(sizeof(ListNode *));
108             p->val = num - 10;
109             r->next = p;
110             r = p;
111             flag = 1;
112         }
113         l2 = l2->next;
114 
115     }
116     if (flag) //最后再判断一次判断是否有进位
117     {
118         p = (struct ListNode *)malloc(sizeof(ListNode *));
119         p->val = 1;
120         r->next = p;
121         r = p;
122     }
123     r->next = NULL;
124     return h->next;
125 }
126 int _tmain(int argc, _TCHAR* argv[])  //测试函数
127 {
128     Lnode t1,t2,t;
129     t1 = create();
130     t2 = create();
131     t = addTwoNumbers(t1->next,t2->next);
132     print(t);
133     return 0;
134 }