链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。其特点是查询效率慢，时间复杂度为O(n)，但是增加和删除的快，时间复杂度为O(1)。

2、两数相加

image.png

分析

简单分析，可以通过双指针的形式来处理这类问题，但是最开始的时候我并不想重新创建一个新的链表，因为那会耗费空间，而且题意上也没有说明两个链表的长度是相同的，因此我一直以为是相同的，所有我就把表一作为修改的表，但是提交上去才发现链表是不等长的，于是，我只能重新创建一个新的链表。
建立新链表之后，要处理进位问题相应的进位问题，而且新链表遍历完两个链表之后，如果还产生进位，又需要创建新的节点来进行保存。

题解一

  1. class Solution {
  2. public:
  3.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  4.         ListNode* temp=new ListNode();
  5.         ListNode* res=temp;
  6.         ListNode* t1=l1;
  7.         ListNode* t2=l2;
  8.         int num=0;
  9.         while(t1!=NULL&&t2!=NULL){
  10.             temp->next=new ListNode();
  11.             temp=temp->next;
  12.             if(num>0){
  13.                 temp->val=(t1->val+num+t2->val)%10;
  14.             }
  15.             else {
  16.                 temp->val=(t1->val+t2->val)%10;
  17.             }
  18.             if(t1->val+num+t2->val>=10){
  19.                 num=1;
  20.             }else{
  21.                 num=0;
  22.             }
  23.             t1=t1->next;
  24.             t2=t2->next;
  25.         }
  26.         while(t1!=NULL){
  27.             temp->next=new ListNode();
  28.             temp=temp->next;
  29.             if(num>0){
  30.                 temp->val=(t1->val+num)%10;
  31.             }
  32.             else 
  33.                 temp->val=(t1->val)%10;
  35.             if(t1->val+num>=10){
  36.                 num=1;
  37.             }else{
  38.                 num=0;
  39.             }
  40.             t1=t1->next;
  41.         }
  42.         while(t2!=NULL){
  43.             temp->next=new ListNode();
  44.             temp=temp->next;
  45.             if(num>0){
  46.                 temp->val=(t2->val+num)%10;
  47.             }
  48.             else 
  49.                 temp->val=(t2->val)%10;
  50.             if(t2->val+num>=10){
  51.                 num=1;
  52.             }else{
  53.                 num=0;
  54.             }
  55.             t2=t2->next;
  56.         }
  57.         if(num>0){
  58.             temp->next=new ListNode();
  59.             temp=temp->next;
  60.             temp->val=num;
  61.         }
  62.         return res->next;
  63.     }
  64. };

这是我的题解，这没有经过任何的优化，但从解答问题入手而已。和题解那些简洁代码相比，有些落后和繁琐了。

题解二

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head=nullptr;
        ListNode* tail=nullptr;
        int num=0;
        while(l1||l2){
            int n1=l1?l1->val:0;
            int n2=l2?l2->val:0;
            int sum=(n1+n2+num)%10;
            if(!head){
                head=new ListNode(sum);
                tail=head;
            }else{
                tail->next=new ListNode(sum);
                tail=tail->next;
            }
            num=(n1+n2+num)/10;
            if(l1){
                l1=l1->next;
            }
            if(l2){
                l2=l2->next;
            }
        }
        if(num>0){
            tail->next=new ListNode(num);
        }
        return head;
    }
};

这是官方的题解，因为循环中存在大量的比较，所以实际运行效率低于我所写的题解，但是代码量少，十分简洁。

题解三

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode();
        int n1 = 0, n2 = 0, carry = 0;
        ListNode* current = head;
        while(l1!=nullptr||l2!=nullptr||carry!=0)
        {
            if(l1==nullptr)
            {
                n1 = 0;
            }
            else
            {
                n1 = l1->val;
                l1 = l1->next;
            }
            if(l2==nullptr)
            {
                n2 = 0;
            }
            else
            {
                n2 = l2->val;
                l2 = l2->next;
            }
            current->next = new ListNode((n1+n2+carry)%10);
            current = current->next;
            carry = (n1+n2+carry)/10;
        }
        return head->next;
    }
};

这是其他人写的题解，比官方的好了许多，而且减少了很多比较。