2.两数相加（单链表）

【题目】

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

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

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

【示例】

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

【提示】

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

【自己的想法】

因为是倒序，所以反而更好相加一些，都从链表的头节点开始加。定义一个变量存储进位。一边遍历一遍相加。时间复杂度就是O(n)。

【困难，，，哈哈哈这都有困难，我真的服了我自己】

：指针的移动问题？怎么把这个数返回回去呢？

：傻了，直接加个头指针不就好了，用尾指针进行移动复制。

：相加的时候 x=*l1+*l2+tmp 报错。

：呵呵呵，l1和l2是节点指针，也就是节点值的地址...想取值应该是写l2->val。而且也不能这么写，因为l1和l2此时可能是NULL节点。

：超出时间限制。。。

if(l2==NULL){
                tail->next=new ListNode(l1->val);
                tail=tail->next;
            }
//这是错的，这是错的！

：如果有一方结束的判断语句肯定不能判断是空，是判断还有值.....而且知道不为NULL后应该直接移动l1或者l2的指针，让其再次进入while循环，不是又赋值。

【代码，只能说自己敲一遍还是能发现不少问题的。。。不然真的不敢相信我对链表已经忘得啥也不剩了】

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head=NULL;
        ListNode* tail=NULL;
        int tmp=0;//进位
        while(l1||l2){//只要l1和l2中有一个没有遍历完，就继续
            int n1=l1?l1->val:0;
            int n2=l2?l2->val:0;
            int x=n1+n2+tmp;
            //把头节点分开
            if(head==NULL){
                head=tail= new ListNode(x%10);
            }
            else{
                tail->next=new ListNode(x%10);
                tail=tail->next;
            }
            tmp=x/10;
            //移动指针
            if(l1){
                l1=l1->next;
            }
            if(l2){
                l2=l2->next;
            }
        }
        //不要忘了最高位
        if (tmp>0) {
            tail->next = new ListNode(tmp);
        }
        return head;
    }
};

【趁此机会，复习一下单链表】

#include <iostream>
using namespace std;

// 1. 节点
struct node{
	int num;
	node* next;
}; 

// 2. 链表
class LinkList{
	private:
		node* head;
		int length;
	public:
		LinkList();
		~LinkList();
		void creatList();//创建链表
		void dispList();
		int listLength(); 
		bool isEmpty(); 
		int getIndexByElem(int e);
		bool Insert(int i,int e);
		bool Delete(int i);
}; 

// 3. 构造函数
LinkList::LinkList(){
	head=new node();
	head->next= NULL;
	length=0;
} 

// 4. 析构函数
LinkList::~LinkList(){
	node *p1,*p2;
	p1=head;
	p2=head->next;
	while(p2!=NULL){
		delete p1;
		p1=p2;
		p2=p2->next; 
	}
	delete p2;
} 

// 5. 尾插法创建链表
void LinkList::creatList(){
	node *p1,*p2;
	p2=head;//p2指向尾节点 
	int tmp;
	cout<<"请输出要插入的值（按回车键结束）：";
	while(cin>>tmp){
		p1=new node();
		p1->num=tmp;
		p2->next=p1;
		p2=p1;
		length++;
		if(cin.get()=='\n') break;
	}
	p2->next=NULL;
} 

// 6. 输出单链表
void LinkList::dispList(){
	node *p;
	p=head->next;
	while(p!=NULL){
		cout<<p->num<<" ";
		p=p->next;
	}
	cout<<endl;
} 

// 7. 单链表长度
int LinkList::listLength(){
	return length;
} 

// 8. 判断链表是否为空
bool LinkList::isEmpty(){
	if(length) return 1;
	else return 0;
} 

// 9. 查找元素(返回下标)
int LinkList::getIndexByElem(int e){
	node *p;
	int i=1;
	p=head->next;
	while(p!=NULL){
		if(p->num==e){
			return i;
		} 
		i++;
		p=p->next;
	}
	return -1;
}

// 10. 插入元素
bool  LinkList::Insert(int i,int e){
	node *p1,*p2;
	int j=1;
	p1=head; //从head开始，可以插到最前面
	while(p1!=NULL){
		if(j==i){
			p2=new node();
			p2->num=e;
			p2->next=p1->next;
			p1->next=p2;
			return 1;
		}
		j++;
		p1=p1->next;
	} 
	return 0;
}

// 11. 删除元素
//  head->1->2->3
// 删除1
// p1=head p2=p1->next=1
// p1->next=p2->next 
bool LinkList::Delete(int i){
	node *p1,*p2;
	p1=head;
	int j=1;
	while(p1!=NULL){
		if(j==i){
			p2=p1->next;
			if(p2!=NULL){
				p1->next=p2->next;
				delete p2;
				return 1;
			}
			
		}
		j++;
		p1=p1->next;
	}
	return 0;
} 


// test
int main(){
	LinkList test;
	test.creatList();// 1 2 3 4 5 6
	test.Insert(4,8); // 1 2 3 8 4 5 6
	test.getIndexByElem(4);// 5
	test.dispList();
	test.Delete(2);// 1 3 8 4 5 6
	test.dispList();
} 
 

测试没毛病。

【感想】

拖了好几天，感觉自己前两年不知道在干啥，对学过的知识都好陌生。

NULL不能小写，小写就写nullptr。而且nullptr更好，表示空指针，而NULL就是0。