LeetCode之Add Two Numbers

Add Two Numbers

方法一:

  考虑到有进位的问题,首先想到的思路是:

  先分位求总和得到 totalsum,然后再将totalsum按位拆分转成链表;

 1 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
 2         int sum = 0;
 3         int i = 1;
 4         while(l1 != NULL && l2 != NULL)
 5         {
 6             sum += i*(l1->val + l2->val);
 7             i *= 10;
 8             l1 = l1->next;
 9             l2 = l2->next;
10         }
11         while(l1 != NULL)
12         {
13             sum += i * (l1->val);
14             i *= 10;
15             l1 = l1->next;
16         }
17         while(l2 != NULL)
18         {
19             sum += i * (l2->val);
20             i *= 10;
21             l2 = l2->next;
22         }
23         //fen
24         ListNode *head = new ListNode(0);
25         ListNode *p = head;
26         if(sum == 0) return head;
27         while(sum!=0)
28         {
29           p->next = new ListNode(sum%10);
30           p = p->next;
31           sum /= 10;
32         }
33         return head->next;
34     }

  修修改改总算是通过了基本测试,但并不是100%通过;

  这就奇怪了,为什么运算得好好的,遇到这组测试就偏偏出了问题。输出中间结果一看,才知道是 int 型溢出了。因此将变量 sum 和变量 i 都从int型换成 long long 型。这下总该行了吧?

  没想到呀,还有更长的测试数据。

  静下心来想一想,既然输入的数据是链表的形式,必然会有超过 long long 长度的情况。此解决方案存在巨大的隐患!!!

方法二:

  换一种思维方式,只需要关注同等位的相加,进位1或者不进位。问题很简单嘛,同等位相加加入到新链表中,若有进位则记录到下次同等位的相加中....

 1 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
 2         ListNode *head = new ListNode(0);
 3         ListNode *p = head;
 4         int sum = 0;
 5         while(l1 != NULL || l2 != NULL)
 6         {
 7             if(l1 != NULL)
 8             {
 9                 sum += (l1->val);
10                 l1 = l1->next;
11             }
12             if(l2 != NULL)
13             {
14                 sum += (l2->val);
15                 l2 = l2->next;
16             }
17             p->next = new ListNode(sum%10);
18             p = p->next;
19             sum /= 10;
20         }
21         if(sum != 0)
22             p->next = new ListNode(sum);
23         return head->next;
24     }

 基础补充

  回顾下链表的创建个输出,以头结点不存内容为例。

1、链表的创建:

 1 ListNode* CreatList()
 2 {
 3   ListNode *head = new ListNode(0);
 4   ListNode *p = head;
 5   int x = 1;
 6   while(1)
 7   {
 8     cin>>x;
 9     if(x == -1)
10       break;
11     p->next = new ListNode(x);
12     p = p->next;
13   }
14   return head;
15 }

2、打印链表:

 1 void PrintList(ListNode *head)
 2 {
 3   ListNode* p = head;
 4   while(p->next!=NULL)
 5   {
 6     p = p->next;
 7     cout<<p->val<<"->";
 8   }
 9   cout<<endl;
10 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 86 Partition List

Given a linked list and a value x, partition it such that all nodes less than x...

1906
来自专栏Jack-Cui

234. Palindrome Linked List(Linked List-Easy)

Given a singly linked list, determine if it is a palindrome. Follow up: Could yo...

19610
来自专栏Jack-Cui

160. Intersection of Two Linked Lists(Linked List-Easy)

    Write a program to find the node at which the intersection of two singly lin...

2265
来自专栏小二的折腾日记

LeetCode-23-Merge-k-Sorted-Lists

这个题乍一看只是对链表的一个排序,因为是很多个链表,所以很简单的想法就是将整个数组里面的两个链表分别进行排序。两个两个互相排序之后就能排好。这里用的是递归。当v...

842
来自专栏WD学习记录

LeetCode Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers....

871
来自专栏深度学习与计算机视觉

数据结构-单链表的读取,插入与删除

链表定义: struct ListNode { int value; ListNode *next; }; 单链表读取 在顺序存储结构中,比如数组中,想...

2147
来自专栏书山有路勤为径

链表求环

LeetCode 141. Linked List Cycle 142.Linked List Cycle II

862
来自专栏计算机视觉与深度学习基础

Leetcode 61 Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative...

20610
来自专栏desperate633

LintCode 合并k个排序链表题目分析代码

样例 给出3个排序链表[2->4->null,null,-1->null],返回 -1->2->4->null

892
来自专栏desperate633

LeetCode 160. Intersection of Two Linked Lists题目分析

请写一个程序,找到两个单链表最开始的交叉节点。 ** 注意事项 ** 如果两个链表没有交叉,返回null。 在返回结果后,两个链表仍须保持原有的结构。 ...

912

扫码关注云+社区

领取腾讯云代金券