今日刷题
2个逆序的链表，要求从低位开始相加，得出的结果也逆序输出，返回值是逆序结果链表的头结点。
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
解题思路：
需要注意各种进位情况。如特殊情况：
Input: (9 -> 9 -> 9 -> 9 -> 9) + (1 -> )
Output: 0 -> 0 -> 0 -> 0 -> 0 -> 1
为了处理?法统?，可以先建??个虚拟头结点，这个虚拟头结点的 Next 指向真正的 head，这样
head 不需要单独处理，直接 while 循环即可。另外判断循环终?的条件不?是 p.Next ！= nil，这样最
后?位还需要额外计算，循环终?条件应该是 p != nil。
示例代码：
class addTwoNumbers{
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* re = new ListNode(0);
ListNode* r = re;
int carry = 0;
while(l1!=NULL || l2!=NULL)
{
int x = 0;
int y = 0;
if(l1!=NULL)
{
x = l1->val;
}else{
x = 0;
}
if(l2!=NULL)
{
y = l2->val;
}else{
y = 0;
}
int s = carry + x + y;
carry = s/10;
r->next = new ListNode(s%10);
r = r->next;
if(l1!=NULL)
{
l1 = l1->next;
}
if(l2!=NULL)
{
l2 = l2->next;
}
}
if(carry > 0){
r->next = new ListNode(carry%10);
}
return re->next;
}
};
预备知识：链表。
一、链表形象解释
可以想象：有一个小纸条，上面写着一个抽屉的地址，那个抽屉里有一些你需要的东西和一个新的写着地址的小纸条，这个小纸条又指向了一个新的抽屉。
二、链表c++演示
1.链表基本数据结构
struct ListNode
{
double value;
ListNode *next;
};
可以看出：ListNode 结构有一个有趣的属性，它包含一个指向相同类型数据结构的指针
（1）单个节点存放的值可以一个结构体，或者你想要的数据类型，
（2）另外也可加入指向上一个节点的指针
struct data
{
int number;
string name;
string sex;
};
struct ListNode
{
struct data *info;
ListNode *next;
ListNode *last;
};
2.创建链表(单链表)
（1）创建头节点head，并且将当前结点p指向头结点（p=head）
（2）创建下一个结点q，当前结点p的下一结点为q（p->next=q）
（3）结点p后移一位（p = p->next）
#include <iostream>
#include<vector>
using namespace std;
struct ListNode{
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL){
}
};
int main()
{
int num;
cin >> num;
ListNode* head = new ListNode(num);
ListNode* p = head;
//利用尾插法创建一个链表
while (cin >> num){
ListNode* q = new ListNode(num);
p->next = q;
p = p->next;
}
//遍历这个链表，并输出每个结点的元素
ListNode* m = head;
while (m != nullptr){
cout << m->val << endl;
m = m->next;
}
return 0;
}
3.插入节点
1.判断原链表是否是空链表，如果是，将head指向新增结点
2.如果不是空链表，向链表尾部插入新结点
ListNode* insertNode(ListNode* head, int data){
ListNode* newNode = new ListNode(data);
ListNode* p = head;
if (p == nullptr){
head = newNode;
}
else{
while (p->next != nullptr){
p = p->next;
}
p->next = newNode;
}
return head;
}
4.删除节点
基本思路：如果链表中有待删除的节点，则遍历到待删除的节点的上一个节点，并将该节点的next指针指向要删除节点的下一个节点。
ListNode* deleteNode(ListNode* head, int data){
ListNode* p = head;
//首先判断是不是空链表
if (p == nullptr){
return head;
}
else{
//判断是不是删除头节点
if (p->val == data){
head = p->next;
delete p;
return head;
}
else{
//如果有该结点，遍历到待删除节点的前一节点
while (p->next != nullptr && p->next->val != data){
p = p->next;
}
//遍历完整个链表都没有待删除节点
if (p->next == nullptr){
return head;
}
else{
ListNode* deleteNode = p->next;
p->next = deleteNode->next;
delete deleteNode;
return head;
}
}
}
}
参考：
https://blog.csdn.net/slandarer/article/details/91863177