一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 319|回复: 5
收起左侧

[算法题] 请教一道题

[复制链接] |试试Instant~ |关注本帖
chekie 发表于 2016-4-4 05:59:16 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚开始刷题。第二题addTwoNumbers。单独test case都没问题,就是提交的时候run time error. last executed input:

[1,1,0,4,7,2,7,3,0,1][2,5,5,6,8,0,3,0,5,1]




我的code(c):

  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. *     int val;
  5. *     struct ListNode *next;
  6. * };
  7. */
  8. struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
  9.     struct ListNode *result = NULL, *iter, *node;
  10.     int carry = 0, sum, op1, op2;
  11.     while (l1 != NULL || l2 != NULL) {
  12.         if (l1 != NULL) {
  13.             op1 = l1->val;
  14.             l1 = l1->next;
  15.         }
  16.         else {
  17.             op1 = 0;
  18.         }
  19.         if (l2 != NULL) {
  20.             op2 = l2->val;
  21.             l2 = l2->next;
  22.         }
  23.         else {
  24.             op2 = 0;
  25.         }
  26.         sum = (op1 + op2 + carry)%10;
  27.         carry = (op1 + op2 + carry)/10;
  28.         node = (struct ListNode *)malloc(sizeof(struct ListNode));
  29.         node->val = sum;
  30.         if (result == NULL) {
  31.             result = node;
  32.             iter = result;
  33.         }
  34.         else {
  35.             iter->next = node;
  36.             iter = node;
  37.         }
  38.     }
  39.     if (carry == 1) {
  40.         node = (struct ListNode *)malloc(sizeof(struct ListNode));
  41.         node->val = 1;
  42.         iter->next = node;
  43.     }
  44.     return result;
  45. }
复制代码
大家帮我看看啥问题。

谢谢!
stellari 发表于 2016-4-4 07:33:50 | 显示全部楼层
本帖最后由 stellari 于 2016-4-4 07:57 编辑

你在新创建node的时候,没有初始化next成员。
对于链表中间的node,这没问题,因为反正该成员稍后就会被写入正确值;但是最后一个节点的next则不会被正确赋值。

简单地,你在所有的node->val的下面加上一句node->next=NULL;即可
回复 支持 反对

使用道具 举报

 楼主| chekie 发表于 2016-4-4 07:41:52 | 显示全部楼层
iter的初始值会在添加第一个result node的时候完成。就是判断result == NULl的时候。
好像不是这个问题,刚试了一下把iter 和 node在定义的时候初始为NULL,一样不给提交
回复 支持 反对

使用道具 举报

 楼主| chekie 发表于 2016-4-4 07:43:58 | 显示全部楼层
奇怪的是如果我把

[1,1,0,4,7,2,7,3,0,1]
[2,5,5,6,8,0,3,0,5,1]

单独拿出来测试结果是对的。
回复 支持 反对

使用道具 举报

stellari 发表于 2016-4-4 08:07:15 | 显示全部楼层
chekie 发表于 2016-4-4 07:43
奇怪的是如果我把

[1,1,0,4,7,2,7,3,0,1]

请看2楼的修改答案。你在仅测试一两个用例时,很大概率会正好被分配到一些内容全为0的内存空间,这时next会正好是NULL,因此就能够通过。但是一旦测试比较多用例时,就很难保证每一次分配都在全0空间上,这时出错也就不奇怪了。
回复 支持 反对

使用道具 举报

 楼主| chekie 发表于 2016-4-4 08:10:47 | 显示全部楼层
果然是。
之前习惯是malloc之后memset成0.这次居然忘了。
谢谢啊!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 05:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表