每周一道算法題,今天這個(gè)算法題做完后和大家討論了會(huì),優(yōu)化了下代碼,所以就搞的比較晚了(我能說我不懂鏈表,研究了一上午的鏈表么)
題目是這樣的:
給你兩個(gè)非空鏈表(鏈表不懂的自行百度,簡(jiǎn)單的說就是一個(gè)結(jié)構(gòu)體,里面有數(shù)據(jù)和一個(gè)指針,指針指向下一個(gè)結(jié)構(gòu)體,所以地址可以不連續(xù)),每個(gè)鏈表代表一個(gè)數(shù),把這兩個(gè)數(shù)加起來,返回結(jié)果.結(jié)果也是以鏈表的形式返回(給的數(shù)據(jù)不會(huì)以0開頭,唯一以 0 開頭的情況是數(shù)字0本身,所以不用擔(dān)心前面有多余0的情況).
直接上我的答案
//創(chuàng)建鏈表
struct ListNode* alloc_node(int val){
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->next = NULL;
node->val = val;
return node;
}
//遞歸將兩個(gè)鏈表的數(shù)加起來
void sum_node(struct ListNode* l1, struct ListNode* l2,struct ListNode* l3,int val)
{
l3->val = val;
if(l1) l3->val += l1->val;
if(l2) l3->val += l2->val;
if (l3->val >= 10){
l3->val -= 10;
val = 1;
}else {
val = 0;
}
if ((l1 ?l1->next : 0)|| (l2?l2->next:0) || val) {
l3->next = alloc_node(0);
sum_node(l1?l1->next:NULL,l2?l2->next:NULL,l3->next,val);
}
}
//題目:給兩個(gè)鏈表,要求返回一個(gè)鏈表
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* l3 = alloc_node(0);
sum_node(l1,l2,l3,0);
return l3;
}
我是用C寫的遞歸,不用遞歸效率會(huì)更高,不過可讀性差了點(diǎn),然后不得不感嘆C的效率還是遠(yuǎn)勝過swift啊(就這道題來說至少快了3倍,注意是至少),不過還是得學(xué),這兩天用swift仿寫了一個(gè)demo,這周抽時(shí)間再和大家分享下,還是蠻有意思的一個(gè)小demo.
