首页 > 代码库 > [LeetCode]Add Two Numbers
[LeetCode]Add Two Numbers
链表的数据对应位置相加，之和组成新的链表，已经说过是非负的值。
题目不难，注意链表的操作。
本人觉得平时练习有时间，即便题目说链表不为空，我们也应该判断一下，养成良好的习惯很重要。
说一下注意点：
1.主要考虑进位
2.注意可能链表不一样长
3.注意不要忘记了最高位的进位
这里用的是尾插法，可以考虑用头插法试试。
1 /***************************************
2 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 contain a single digit. Add the two numbers and return it as a linked list.
3 You may assume the two numbers do not contain any leading zero, except the number 0 itself.
4
5 Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
6 Output: 7 -> 0 -> 8
7 ***************************************/
8
9 /**
10 * Definition for singly-linked list.
11 * struct ListNode {
12 * int val;
13 * struct ListNode *next;
14 * };
15 */
16 #include<stdio.h>
17
18 struct ListNode {
19 int val;
20 struct ListNode *next;
21 };
22
23 struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
24 if(l1 == NULL)return l2;
25 if(l2 == NULL)return l1;
26 int j = 0;//record carry value记录进位值
27 struct ListNode* ln = (struct ListNode *)malloc(sizeof(struct ListNode));
28 struct ListNode* p = ln;
29 struct ListNode* p1 = l1;
30 struct ListNode* p2 = l2;
31 int i = p1->val + p2->val + j;
32 p->val = i%10;
33 j = i/10;
34 p1 = p1->next;
35 p2 = p2->next;
36 while(p1 != NULL && p2 != NULL){//尾插法
37 struct ListNode *q = (struct ListNode *)malloc(sizeof(struct ListNode));
38 p->next = q;
39 p=q;
40 i = p1->val + p2->val + j;
41 p->val = i%10;
42 j = i/10;
43 p1 = p1->next;
44 p2 = p2->next;
45 }
46
47 while(p1 != NULL){//l1剩余未转换完的数字
48 struct ListNode *q = (struct ListNode *)malloc(sizeof(struct ListNode));
49 p->next = q;
50 p=q;
51 i = p1->val + j;
52 p->val = i%10;
53 j = i/10;
54 p1 = p1->next;
55 }
56 while(p2 != NULL){//l2剩余未转换完的数字
57 struct ListNode *q = (struct ListNode *)malloc(sizeof(struct ListNode));
58 p->next = q;
59 p=q;
60 i = p2->val + j;
61 p->val = i%10;
62 j = i/10;
63 p2 = p2->next;
64 }
65 if(j > 0){//最高位进位
66 struct ListNode *q = (struct ListNode *)malloc(sizeof(struct ListNode));
67 p->next = q;
68 p=q;
69 p->val = j;
70 }
71 p->next = NULL;
72 return ln;
73 }
74
75 int main(){
76 struct ListNode* l1 = (struct ListNode *)malloc(sizeof(struct ListNode));
77 struct ListNode* l2 = (struct ListNode *)malloc(sizeof(struct ListNode));
78 struct ListNode* p1 = l1;
79 struct ListNode* p2 = l2;
80 int i = 3455;
81 int j = 16789;
82 l1->val = i%10;
83 l2->val = j%10;
84 i = i/10;
85 j = j/10;
86 printf("%d:%d\n",p1->val,p2->val);
87 while (i > 0 && j > 0)
88 {
89 struct ListNode* q1 = (struct ListNode *)malloc(sizeof(struct ListNode));
90 q1->val = i%10;
91 i = i/10;
92 p1->next = q1;
93 p1 = q1;
94 struct ListNode* q2 = (struct ListNode *)malloc(sizeof(struct ListNode));
95 q2->val = j%10;
96 j = j/10;
97 p2->next = q2;
98 p2 = q2;
99 printf("%d:%d\n",p1->val,p2->val);
100 }
101 while(i > 0){
102 struct ListNode* q1 = (struct ListNode *)malloc(sizeof(struct ListNode));
103 q1->val = i%10;
104 i = i/10;
105 p1->next = q1;
106 p1 = q1;
107 }
108 while(j > 0){
109 struct ListNode* q2 = (struct ListNode *)malloc(sizeof(struct ListNode));
110 q2->val = i%10;
111 j = j/10;
112 p2->next = q2;
113 p2 = q2;
114 }
115 p1->next = NULL;
116 p2->next = NULL;
117
118 struct ListNode* ap = addTwoNumbers(l1,l2);
119 struct ListNode* aq = ap;
120 p1 = l1;
121 p2 = l2;
122 while(aq != NULL){
123 printf("%d -> ",aq->val);
124 aq = aq->next;
125 }
126
127 while(ap != NULL){
128 aq = ap;
129 ap = ap->next;
130 free(aq);
131 }
132 while(l1 != NULL){
133 p1 = l1;
134 l1 = l1->next;
135 free(p1);
136 }
137 while(l2 != NULL){
138 p2 = l2;
139 l2 = l2->next;
140 free(p2);
141 }
142
143 return 0;
144 }
[LeetCode]Add Two Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。