1.题目

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]

输出：[7,0,8]

解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]

输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

输出：[8,9,9,9,0,0,0,1]

2、解题思路

模拟该过程，自己本地先创建两个链表，然后进行每位数字相加，每相加一次，创建一个节点，让前一个节点指向该节点，依次往后进行，在这里相加过程中需要注意一点，就是两个链表长度可能不一样，要分别对每种情况进行处理，下面显示了该思想的过程：

及从每一位进行相加，若两个链表不一样长，那么多余的那一段就进行加0，最后的到res，但这没处理进位，因此，在上面进行相加之后，我们还需好处理每个节点的进行问题，进位处理其实很简单，就遍历每个节点，若当前节点大于10，就向前进位，若不大于10，就跳过该节点，不进行处理。

3、完整代码

#include
   
    #include
    
     using namespace std;struct ListNode {
        int val;     ListNode *next;     ListNode() : val(0), next(nullptr) {
   }     ListNode(int x) : val(x), next(nullptr) {
   }     ListNode(int x, ListNode *next) : val(x), next(next) {
   } };void creatlist(ListNode *head,int length){
   	ListNode *p =head ; //创建一个指针保存头信息	while (length--) 	{
   		int value;		cin >> value;		ListNode *newNode = new ListNode(value,nullptr); //创建一个新节点		p->next = newNode; //让前一个节点指向下一个节点		p = newNode; //让当前指针指向当前节点	}}class Solution {
   public:	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
   		//创建一个链表用于存放结果        ListNode* p1=l1;        ListNode* p2=l2;        ListNode *res = new ListNode(0,nullptr);        //计算l1和l2的长度        int l1_length=0,l2_length=0;        //计算每个节点长度        while(p1)        {
               p1 = p1->next;            l1_length++;                    }        while(p2)        {
               p2=p2->next;            l2_length++;        }        //开始进行节点加法运算         ListNode *start = res;        if(l1_length>l2_length)        {
               while(l2)            {
                   start->val=l1->val+l2->val;                ListNode *tem = new ListNode(0,nullptr);                start->next = tem;                 start= tem;                 l2=l2->next;                l1=l1->next;                               }            while(l1){
                   start->val=l1->val;                if(l1->next!=nullptr)                {
                       ListNode *tem = new ListNode(0,nullptr);                    start->next = tem;                     start= tem;                     l1=l1->next;                }                else                 l1=l1->next;            }        }        else if(l1_length
     
      val=l1->val+l2->val;                ListNode *tem = new ListNode(0,nullptr);                start->next = tem;                 start= tem;                 l2=l2->next;                l1=l1->next;                               }            while(l2){
                   start->val=l2->val;                if(l2->next!=nullptr)                {
                       ListNode *tem = new ListNode(0,nullptr);                    start->next = tem;                     start= tem;                     l2=l2->next;                }                else                 l2=l2->next;            }        }        else        {
                while(l1)            {
                   start->val=l1->val+l2->val;                if(l1->next!=nullptr)                {
                       ListNode *tem = new ListNode(0,nullptr);                    start->next = tem;                     start= tem;                     l2=l2->next;                    l1=l1->next;                }                else                {
                       l2=l2->next;                    l1=l1->next;                }                          }        }        // 处理进位        ListNode *start1 = res;        while(start1)        {
               if(start1->val>=10)            {
                      //处理最后一位大于10的情况                if(!(start1->next))                {
                       ListNode *tem = new ListNode(0,nullptr);                    tem->val = start1->val/10;                    start1->val =  start1->val%10;                    start1->next = tem;                      break;                }                else                {
                       start1->next->val=start1->val/10+start1->next->val;                    start1->val=start1->val%10;                    start1 = start1->next;                    }                            }            else{
                    start1 = start1->next;            }        }		return res;	}};int main(){
   	//创建两个链表	//第一个链表长度，以及链表的创建	ListNode *head = new ListNode(0, nullptr);	int len;	cin >> len;	creatlist(head,len);	//创建第二个链表	ListNode *head2 = new ListNode(0, nullptr);	//第二个链表长度	int len2;	cin >> len2;	creatlist(head2,len2);	Solution p;	ListNode *res = p.addTwoNumbers(head->next, head2->next);    //进行输出	while(res->next)    {
           cout<
      
       val<
       
        next;        if(!res->next)        {
               cout<
        
         val<

注：该代码输入格式：

第一行：第一个链表的个数第二行：第一个链表对应的每个节点的值第三行：第二个链表的个数第四行：第二个链表对应的每个节点的值eg:79 9 9 9 9 9 949 9 9 9

4、结果

在这里插入图片描述

可以看到该代码从整体上效率还是挺高的，但是内存消耗有点大，其次从代码角度来看，该代码其实没有什么太多的含金量，而且写得过于复杂繁琐（一个简单的问题，居然被我码了近200行代码），主要还是对链表理解的不够深入，后续下来还需要多联系一下才行。

转载地址：http://gctii.baihongyu.com/

你可能感兴趣的文章

(function() {}).call(this);立即調用函數有什麼好處，什麼時候應該這樣做