每周一道算法题,今天这个算法题做完后和大家讨论了会,优化了下代码,所以就搞的比较晚了(我能说我不懂链表,研究了一上午的链表么)
题目是这样的:
给你两个非空链表(链表不懂的自行百度,简单的说就是一个结构体,里面有数据和一个指针,指针指向下一个结构体,所以地址可以不连续),每个链表代表一个数,把这两个数加起来,返回结果.结果也是以链表的形式返回(给的数据不会以0开头,唯一以 0 开头的情况是数字0本身,所以不用担心前面有多余0的情况).
直接上我的答案
//创建链表
struct ListNode* alloc_node(int val){
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->next = NULL;
node->val = val;
return node;
}
//递归将两个链表的数加起来
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);
}
}
//题目:给两个链表,要求返回一个链表
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* l3 = alloc_node(0);
sum_node(l1,l2,l3,0);
return l3;
}
我是用C写的递归,不用递归效率会更高,不过可读性差了点,然后不得不感叹C的效率还是远胜过swift啊(就这道题来说至少快了3倍,注意是至少),不过还是得学,这两天用swift仿写了一个demo,这周抽时间再和大家分享下,还是蛮有意思的一个小demo.
