题目:给定两个链表,分别表示两个非负整数。它们的数字逆序存储在链表中,并且每个节点只存储一个数字,计 算两个数的和,并且返回和的链表头指针。
如: 输入:3->6->9,2->5->7,输出:5->1->7->1
思路:1、逆序相加,相当于从两个链表头指针向后依次相加
2、注意两个链表长度可能不同
3、注意可能存在的进位问题
/*创建链表,对应节点相加*/
#include <iostream>
#include <string>
#include <stdlib.h>
typedef struct Node
{
int value;
Node* ptr;
Node(int a)
{
value = a;
ptr = NULL;
}
};
Node* Linkcreate(int* a,int n);
Node* Linkadd(Node* a, Node* b);
void Linkdestory(Node* Linklist);
int main()
{
int a[] = {3,6,9};
int b[] = {2,5,7};
int n1 = sizeof(a) / sizeof(int);
int n2 = sizeof(b) / sizeof(int);
//创建链表
Node* p1=Linkcreate(a,n1);
Node* p2=Linkcreate(b,n2);
//节点相加
Node* p3=Linkadd(p1,p2);
//如果p3=p3->next,p3无法释放
Node* pp = p3->ptr;
if (pp == NULL)
std::cout << "null!" << std::endl;
while (pp != NULL)
{
printf("%d ",pp->value);
pp = pp->ptr;
}
std::cout << " " << std::endl;
//删除链表
//printf("p1\n");
Linkdestory(p1);
//printf("p2\n");
Linkdestory(p2);
//printf("p3\n");
Linkdestory(p3);
system("pause");
return 0;
}
Node* Linkadd(Node* a, Node* b)
{
if (a == NULL)
{
return b;
}
if (b == NULL)
{
return a;
}
Node* head = new Node(0);
Node* p = head;
Node* p1 = a->ptr;
Node* p2 = b->ptr;
int hig = 0;
int tmp;
//若不定义data,p1或p2为NULL的时候->value将无法取值
int data1, data2;
while (p1 != NULL || p2 != NULL||hig!=0)
{
if (p1 == NULL)
data1 = 0;
else {
data1 = p1->value;
p1 = p1->ptr;
}
if (p2 == NULL)
data2 = 0;
else {
data2 = p2->value;
p2 = p2->ptr;
}
tmp =(data1 + data2 + hig) % 10;
p->ptr = new Node(tmp);
p = p->ptr;
hig = (data1 + data2 + hig) / 10;
//std::cout << tmp << std::endl;
}
//p1 = p1->ptr;若放这里,当p1=NULL,p2!=NULL的时候内存泄漏
if(hig==1)
p->ptr = new Node(hig);
return head;
}
void Linkdestory(Node* Linklist)
{
Node* p = Linklist;
Node* next = p->ptr;
while (p->ptr != NULL)
{
Node* next = p->ptr;
std::cout << "ok" << std::endl;
p->ptr=next->ptr;
delete(next);
}
delete(p->ptr);
delete(p);
}
Node* Linkcreate(int* a,int n)
{
if (a==NULL)
{
return NULL;
}
Node* head = new Node(0);
Node* p = head;
for (int i = 0; i < n; i++)
{
p->ptr=new Node(a[i]);
p = p->ptr;
}
return head;
}
我的总结:
1、关于生成一个新节点
一般书上给出的方法都是:Node *s=(struct Node*)malloc(sizeof(struct Node)); s->data = ...; s->next = ...;
本文采用的方式是在结构体中定义了构造函数 Node(int value):data(value),nextPtr(NULL){}
与下面这种写法等价
Node(int value)
{
data=value;
nextPtr=NULL;
}
创建新的节点方法为Node* HeadNode = new Node(0); 提供参数0为节点的data值,nextPtr指向MULL。
2、本文涉及到插入节点,参考代码使用的是头插法,我使用的是尾插法。
可以参照本文学习 http://blog.csdn.net/behanga/article/details/6701495
3、因为我的实现代码中,先接收整形数据,将其生成数组,然后再将其生成链表,涉及到整形数组的传递问题,调试过程中花了一些时间,主要是对指针和数组在C++中作为 参数和返回值还不太熟练。在C++中,数组不是一种类型,因此不能被直接返回,可以返回指向数组的指针。具体参照 http://blog.sina.com.cn/s/blog_6f26189101012111.html问题得到解决。
4、我认为在实现一个功能时,可以先将问题细化成几部分,将要实现的部分先用伪代码按流程列在Main函数中,然后在逐一实现,这样实现起来比较快速,有条理,且易读,暂且不说实现方法的好坏,通过我的主函数,可以一目了然地看出整个功能的实现流程。
参考答案在主函数中边生成数据边插入链表,而我是先接收所有数据,将它们存储在数组中,后再将数组整体的生成链表。这样将两部分功能分开更清晰,但我也为此付出了消耗内存的代价。两种方法各有利弊,需要权衡。