Leetcode 第二章线性表--2.2 单链表--2.2.1 add two numbers--2017/7/25
单链表如下：
// 单链表节点
struct ListNode { //结构体
int val; //数据成员
ListNode *next; //链域
ListNode(int x) : val(x), next(nullptr) { } //初始化构造方法
};
数据结构、算法与应用C++语言描述 P113
问题描述：
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
分析：342+465=807，都是倒序的。
为了解决这种二义性，C++11标准引入了关键字nullptr，它作为一种空指针常量。
问题二：C++ ?表达式
三元运算符（?:)，也称条件运算符，是if...else结构的简化形式。其名称的出处是它带有三个操作数。它可以计算一个条件，如果为真，就返回一个值；如果条件为假，则返回另一个值。其语法如下：
condition?true_value:false_value
问题三：C++初始化单链表
#include <iostream>
using namespace std;
typedef struct _node //类型别名Node
{
char data; //数据域，这里是char类型注意了
struct _node *next; //链域
}Node;
class List //单项链表类
{
public:
List();
~List();
bool Append(char data);//在单链表尾部插入元素
bool InsertAt(int index, char data);//在单链表指定位置插入元素
bool DeleteAt(int index); //删除单链表指定位置元素
bool IsEmpty();//判断单链表是否为空
bool Output();//输出整个单链表
bool OutputAt(int index);//输出链表指定位置元素
bool OutputPos(char data);//输出链表元素位置
int GetLength();// 获取单链表长度
private:
Node* m_pHead; // 单链表头指针
int m_length; // 单链表长度，添加，删除的时候进行更新
};
List::List()
{
m_pHead = nullptr; //默认构造头指针为空，注意了Node* m_pHead，是一个地址
m_length = 0; //长度为0
}
List::~List() //析构函数
{
Node* pNode = m_pHead;
while (pNode)
{
m_pHead = pNode->next;
free(pNode);
pNode = m_pHead;
}
}
bool List::IsEmpty() //判断是否为空
{
return m_length == 0 ? true : false;
}
int List::GetLength() //获取单链表长度
{
return m_length;
}
bool List::Append(char data) //在单链表尾部插入元素
{
Node* pNewNode = new Node; //分配局部变量
if (pNewNode == nullptr)
{
return false;
}
else{
pNewNode->data = data;
pNewNode->next = nullptr;
}
if (m_pHead == nullptr)
{
m_pHead = pNewNode; //头指针指向pNewNode
m_length = 1; //长度也变化
}
else{
Node* pNode = m_pHead; //新的局部变量pNode
while (pNode->next) //遍历单链表，判断是否下一个节点为空
{
pNode = pNode->next;
}
pNode->next = pNewNode;//将新节点插入尾部
m_length++; //更新单链表长度
}
return true;
}
bool List::InsertAt(int index, char data)
{
if (index >= m_length && index <= 0)
return false;
if (m_pHead == NULL)
return false;
Node* pNode = m_pHead;
int count = 1;
while (pNode)
{
pNode = pNode->next;
count++;
if (count == index - 1) // 在插入节点的前一个节点处停止遍历
break;
}
// 分配新节点
Node* pNewNode = new Node;
if (pNewNode == NULL)
{ // 分配新节点失败，返回
return false;
}
else{ //初始化新节点内容
pNewNode->data = data;
pNewNode->next = NULL;
}
// 保存下一个节点的指针
Node* pNextNode = pNode->next;
// 将当前节点指向新节点
pNode->next = pNewNode;
// 将新节点指向下一个节点
pNewNode->next = pNextNode;
return true;
}
bool List::DeleteAt(int index)
{
//极端情况判断
if (m_pHead == NULL)
return false;
if (index > m_length && index <= 0)
return false;
Node* pNode = m_pHead;
int count = 1;
while (pNode->next)
{
//依次走访单链表，在欲删除节点的前一个节点处停止遍历
if (count == index - 1)
break;
pNode = pNode->next;
count++;
}
// 将要删除的节点的下一个节点的指针保存起来，pNode节点现在是要删除节点的前一个节点
Node* pNextNode = pNode->next->next;
free(pNode->next);
m_length--;
pNode->next = pNextNode;
return true;
}
bool List::OutputPos(char data)
{
Node* pNode = m_pHead;
int count = 1;
while (pNode->next)
{
if (data == pNode->data)
break;
pNode = pNode->next;
count++;
}
if (count > m_length)
return false;
cout << "元素" << data << "的位置: " << count << endl;
return true;
}
bool List::OutputAt(int index)
{
if (m_pHead == NULL)
return false;
if (index > m_length && index <= 0)
return false;
Node* pNode = m_pHead;
int count = 1;
while (pNode->next)
{
if (count == index)
break;
pNode = pNode->next;
count++;
}
cout << "第" << index << "个元素: " << pNode->data << endl;
return true;
}
bool List::Output()
{
if (m_pHead == NULL)
return false;
Node* pNode = m_pHead;
int count = 1;
while (pNode)
{
cout << "第" << count << "个元素:" << pNode->data << endl;
pNode = pNode->next;
count++;
}
return true;
}
int main()
{
cout << "(1) 初始化单链表H" << endl;
List list;
cout << "单链表初始化完毕!" << endl;
cout << "\n(2) 依次采用尾插法插入 a,b,c,d,e元素" << endl;
list.Append('a');
list.Append('b');
list.Append('c');
list.Append('d');
list.Append('e');
cout << "\n(3) 输出单链表H" << endl;
list.Output();
cout << "\n(4) 输出单链表H长度" << endl;
cout << "单链表长度: " << list.GetLength() << endl;
cout << "\n(5) 判断单链表H是否为空" << endl;
if (list.IsEmpty())
cout << "单链表为空! " << endl;
cout << "单链表不为空! " << endl;
cout << "\n(6) 输出单链表H的第三个元素" << endl;
list.OutputAt(3);
cout << "\n(7) 输出元素'a'的位置" << endl;
list.OutputPos('a');
cout << "\n(8) 在第四元素位置上插入'f'元素" << endl;
list.InsertAt(4, 'f');
cout << "\n(9) 输出单链表H" << endl;
list.Output();
cout << "\n(10) 删除单链表H的第三个元素" << endl;
list.DeleteAt(3);
cout << "\n(11) 输出单链表H" << endl;
list.Output();
return 0;
}
答案及测试代码：
#include <iostream>
using namespace std;
//LeetCode, Add Two Numbers
//时间复杂度O（m+n）,空间复杂度O（1）
struct ListNode //结构
{
int val; //数据域
ListNode *next; //链域
ListNode(int x) :val(x), next(nullptr){}
};
//下面要定义一个chain类实现单链表,"头指针"指向链表的开始，而最后一个节点的指针域为nullptr
class chain{
public:
chain(); //构造函数
~chain(); //析构函数
void Append(int data);//在单链表尾部插入元素
void Output();//输出整个单链表
ListNode* m_pHead; // 单链表头指针
int m_length; // 单链表长度，添加，删除的时候进行更新
};
chain::chain() //构造函数实现
{
m_pHead = nullptr; //默认构造头指针为空，注意了node* m_phead，是一个地址
m_length = 0; //长度为0
}
chain::~chain() //析构函数
{
ListNode* pNode = m_pHead; //局部变量
while (pNode) //pNode是地址，不是链域值
{
m_pHead = pNode->next;
free(pNode);
pNode = m_pHead;
}
}
void chain::Append(int data) //在单链表尾部插入元素
{
ListNode* pNewNode = new ListNode(data); //分配局部变量
if (m_pHead == nullptr)
{
m_pHead = pNewNode; //头指针指向pNewNode
m_length = 1; //长度也变化
}
else{
ListNode* pNode = m_pHead; //新的局部变量pNode
while (pNode->next) //遍历单链表，判断是否下一个节点为空
{
pNode = pNode->next;
}
pNode->next = pNewNode;//将新节点插入尾部
m_length++; //更新单链表长度
}
}
void chain::Output()
{
ListNode* pNode = m_pHead; //局部变量
int count = 1;
while (pNode)
{
cout << "第" << count << "个元素:" << pNode->val << endl;
pNode = pNode->next;
count++;
}
}
class Solution{
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2){ //输入是指针,返回亦是指针
ListNode dummy(-1); //dummy节点，头节点，可以说没有用的
int carry = 0; //进位,初始化为0
ListNode *prev = &dummy; //把它的地址给prev 注意下面的|| 是或运算 然后那个？：运算就很精妙
for (ListNode *pa = l1, *pb = l2; pa != nullptr || pb != nullptr;
pa = pa == nullptr ? nullptr : pa->next, pb = pb == nullptr ? nullptr : pb->next,
prev = prev->next){
const int ai = pa == nullptr ? 0 : pa->val;
const int bi = pb == nullptr ? 0 : pb->val;
const int value = (ai + bi + carry) % 10; //余数，注意这里加了进位carry
carry = (ai + bi + carry) / 10; //商--进位
prev->next = new ListNode(value); //尾插法
}
if (carry > 0) //如果最后两位相加，还有进位，就再增加一个节点
prev->next = new ListNode(carry);
return dummy.next; //dummy.next是有意义的输出的开始！！！！
}
};
int main(){
chain A;
chain B;
chain C; //结果
cout << "A：" << endl;
A.Append(2);
A.Append(4);
A.Append(3);
A.Output();
cout << "B:" << endl;
B.Append(5);
B.Append(6);
B.Append(4);
B.Output();
Solution mySolution;
C.m_pHead = mySolution.addTwoNumbers(A.m_pHead,B.m_pHead);
cout << "C:" << endl;
C.Output();
return 0;
}
总结：这就是一个两数相加的问题，只不过在单向链表的这个背景下。