LeetCode攀登之旅(1)

2019 年 10 月 5 日
筆記

LeetCode攀登之旅(1)

1.题目

2.解法

2.1 解法一

2.2 解法二

3.结果

4.作者的话

1.题目

Question:

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)  Output: 7 -> 0 -> 8  Explanation: 342 + 465 = 807.

2.解法

2.1 解法一

【Thinking:】

特殊情况:

两个链表开头均为0，直接返回其中一个链表即可；第一个链表开头为0，第二个链表开头不为0，返回第二个链表；第一个链表开头不为0，第二个链表开头为0，返回第一个链表。

其他情况如下：

如上例子所示得到807，然后逆向翻转即可得到7->0->8,那么怎么得到807呢，这个直接看上面Explanation：342+465，那么342与564又怎么得到呢？

很简单，分别对两个链表逆转组合的数即为这两个数，那么在链表操作，又如何得到这两个数？

以其中一个数字342为例子，他是由2*1+4*10+3*100得到的，那么只需要设置个参数t，首次赋值t=1,后面每次乘以10，作累加即可。另外一个数字同此方法，那么两数相加得到807，怎么展开成7、0、8，并分别赋给链表节点呢。

将807每次除以10，所得的余数刚好为7，继续以807/10的结果按照前面操作依次得到0、8；
在每次得到的数字7或者0、8的同时，可通过创建动态链表节点，并赋值即可。

到这里就有问题了，你怎么保证两数相加所得到的数不超过int范围。。。万一所给的链表很长，岂不是一下子就越界了。。那么以下代码运行就出现了这种问题。。所以不建议。

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {      struct ListNode* p=(struct ListNode*)malloc(sizeof(struct ListNode));      struct ListNode *s, *r=p;  //r 为表尾指针      int t=1;      int a=0,b=0,c;      if(l1->val==0&&l2->val==0)      {          return l1;      }      else if(l1->val==0&&l2->val!=0)      {          return l2;      }      else if(l1->val!=0&&l2->val==0)      {          return l1;      }      else      {          while(l1)          {              a += t*(l1->val);              l1 = l1->next;              t *= 10;          }          t=1;          while(l2)          {                b += t*(l2->val);              l2 = l2->next;              t *= 10;          }          c = a + b;          while(c)          {              s=(struct ListNode *)malloc(sizeof(struct ListNode));              s->val=c%10;              r->next=s;              r=s;              c=c/10;          }          r->next = NULL;          return p->next;        }    }

2.2 解法二

【Thinking:】

特殊情况：链表一为空，返回链表二；链表二为空，返回链表一；

当链表一或者链表二一开始都不为空时，思考如下：

# 正方向直接算结果  (2 -> 4 -> 3)  (5 -> 6 -> 4)  (7 -> 0 -> 8)

那就是，当对应位置上的数相加超过10，就会使得下一位+1，有点类似于普通的两数相加，只不过反过来了。看出以上规律了？

那么我们这里很明确，因为当前位置上的数，最多两个9，和最大18，向后进位最多1，也就是当前位置上的两个数之和只要超过10，那么让他往后加上一个flag数即可，此处的flag为0或者1。

当前位置最终的数为两个链表对应位置数之和除以10的余数！

下一位是否进位通过前面一位对应两个链表相加，除以10的结果向前取整！

【c语言实现】

那么接下来，进入算法实现环节，首先来看c语言实现：

定义一个头结点head，并赋初值为0，可以不赋值；
定义动态节点s，此节点对应的值为每次两链表运算所得的数；
定义r节点，表示尾节点，采用尾插法，每次链向s；
特殊情况处理；
两链表循环内部操作；
利用尾节点直接指向头节点的下一个节点，并释放头结点，返回r所指的head的下一个节点，即为最终结果。

struct ListNode * addTwoNumbers( struct ListNode * l1, struct ListNode * l2 )  {      struct ListNode * head, *r, *s;      int tr;      head = (struct ListNode *)malloc( sizeof(struct ListNode) );      head->val = 0;      r = head;      if (l1 == NULL)          return(l2);      if (l2 == NULL)          return(l1);      int tsum;      int flag = 0;      while (l1||l2)      {          tsum = 0;          if (l1)          {              tsum += l1->val;              l1 = l1->next;          }          if (l2)          {              tsum += l2->val;              l2 = l2->next;          }          tr = (tsum + flag) % 10;          flag = (int) ( (tsum + flag) / 10);          s = (struct ListNode * ) malloc( sizeof(struct ListNode) );          s->val = tr;          r->next = s;          r = r->next;      }      if ( flag )      {          s = (struct ListNode *)malloc( sizeof(struct ListNode) );          s->val = 1;          r->next = s;          r = s;      }      r->next = NULL;      r = head->next;      free(head);      return(r);  }

【python语言实现】

c与py链表操作不同

python链表操作与c语言链表操作不同，在python中直接使用ListNode(0)即可表示为当前节点赋值为0,并同时创建了当前节点。同理，c语言与python语言的next操作也不一样！

整除，c语言中使用int强制从float转换，而python中使用两个/，即//直接返回向下取整结果。

其余思想同上！

# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def addTwoNumbers(self, l1, l2):          """          :type l1: ListNode          :type l2: ListNode          :rtype: ListNode          """          if l1 is None:              return l2          if l2 is None:              return l1          head = ListNode(0)          r = head          flag=0          while l1 or l2:              tsum = 0              if l1:                  tsum += l1.val                  l1=l1.next              if l2:                  tsum += l2.val                  l2=l2.next              tr = ((tsum + flag) % 10)              flag = ((tsum + flag) // 10)              r.next = ListNode(tr)              r = r.next          if flag:              r.next = ListNode(1)          r = head.next          del head          return r

3.结果

LeetCode中，c语言第一次通过击败人数才60%左右，再次提交就100%了。哈哈~~~

c提交图

python通过后，第一次击败人数95.74%，后面再提交58%。。然后再提交，就又高了，很不准确~~~

python提交图

4.作者的话

最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！

更多刷题，请关注本公众号算法系列！