我有两个链表,按照从最重要到最不重要的顺序表示十进制数字的数字。 例如4->7->9->6
和5->7
答案应该是4->8->5->3
而不反转列表,因为反转列表会导致效率降低。
我正在考虑使用stack解决问题。我将遍历两个列表并将数据元素推送到两个单独的堆栈中。每个链接列表。然后我将两个堆栈一起弹出并添加两个元素,如果结果是两位数字没有I 10对其进行模数并将进位存储在临时变量中。余数存储在节点中,并将进位添加到下一个总和,依此类推。 如果两个堆栈是s1和s2,结果链接列表是res。
temp = 0; res = (node*)(malloc(sizeof(node*)); while(s1->top!=-1 || s2->top!=-1) { temp = 0; sum = pop(s1) + pop(s2); n1 = (node*)(malloc(sizeof(node*)); temp = sum/10; sum = sum%10; sum = sum+temp; n1->data = sum; n1->next = res; res = n1; free n1; //temp=0; } if((s1->top==-1)&&(s2->top==-1)) { return res; } else if(s1->top==-1) { while(s2->top!=-1) { temp = 0; sum = pop(s2); sum = sum + temp; temp = sum/10; sum = sum%10; n1 = (node*)(malloc(sizeof(node*)); n1->data = sum; n1->next = res; res = n1; free n1; } } else { while(s2->top!=-1) { temp = 0; sum = pop(s2); sum = sum+temp; temp = sum/10; sum = sum%10; n1=(node*)(malloc(sizeof(node*)); n1->data = sum; n1->next = res; res = n1; free n1; } } return res;
我在面试问题中多次遇到过这个问题,但这是我能想到的最好的解决方案。 如果有人能在ci中找到更高效的东西,那将非常高兴。
两次传球,没有筹码:
这就是我要解决这个问题的方法:
第1步:在两个链接列表上传递,查找长度
说len(L1) = m and len(L2) = n
第2步:找出长度差异
if ( m > n ) d = m - n else if ( n > m ) d = n - m else d = 0
第3步:将临时指针d移到较大列表之前
第4步:现在我们有两个链接列表添加其长度相同,所以递归添加它们,保持进位。
第5步:( 注意:如果(d == 0)不执行此步骤)
在第4步之后,我们有了部分输出列表,现在我们必须将更大的列表的剩余部分放在输出列表的开头。
if ( d > 0 ) -Travel larger list till d positions recursively -Append sum = value_at_end + carry (update carry if sum >= 10) to output list at beginning -Repeat until difference is consumed
注意:我正在解决问题,因为它摆在我面前,而不是建议基础数据结构的变化。
时间复杂度:
总计: O( (m+n) + (n) + (d) )
或O(m+n)
空间复杂度:
总计: O(n + d)
OR O(n)
我只是分别找到每个链表的总值,将它们加在一起,然后将该数字转换为新的链表。 因此,将4-> 7-> 9-> 6和5-> 7分别转换为值为4796和57的整数。 将它们一起添加到4853,然后将其转换为包含4-> 8-> 5-> 3的链表。 您可以使用简单的数学运算进行转换。
如果您改变数字首先表示的方式,那么按照自己的方式进行操作会容易得多。 这样,数字总是第一位,然后是十位数,接着是数百位,等等。
编辑:因为你显然使用了大量的数字:你有没有考虑过制作双链表? 那么你本身就不需要逆转它了。 只是向后移动它。
使用堆栈并不比反转列表更有效(实际上它正在反转列表)。 如果您的堆栈对象是动态分配的,这没什么大不了的,但如果您使用调用递归创建它,您将很容易获得错误排序的堆栈溢出 。 ?
如果您双重链接列表,您可以添加数字并使用向后链接找出放置您的值的位置。
需要了解更多c/c++开发分享在C中有效地添加两个链表,也可以关注C/ C++技术分享栏目—计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享在C中有效地添加两个链表相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/979931.html