2. Add Two Numbers
2017-10-26 本文已影响1人
ciantian
最近再刷leetcode,用除了链表之外的都用python 实现,贴出一些代码,希望指正.
问题描述: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.
简单理解就是用链表实现和操作.
样例输入:Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
算法思想:
- 链表的遍历操作.
- 进位操作,设置一个标志位,默认为0,大于10则进位,算完之后标志位清零.
- 注意链表的长度,有的时候某一个链表先遍历完,需要继续遍历另外一个.
- 合成的链表按照尾插法的形式建立.
/*
问题描述:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
算法思想:
1. 先用尾插法建立(头指针不为空)的两个链表
2. 同时遍历相加 遇到大于等于十的更改标志位,进一.
*/
#include <stdio.h>
#include <stdlib.h>
/*
链表操作 简记.
1. 创建结构体
*/
//1. 创建结构体
typedef struct ListNode
{
int val;
struct ListNode *next;
}linklist;
//定义方法
linklist * CreateList_Front();
linklist * CreateList_End();
linklist * CreateList_End_F_N();
void ShowLinklist(linklist*h);
linklist * SumTwoList(linklist*list1,linklist*list2);
int main()
{
linklist *head;
// head = CreateList_End();
// ShowLinklist(head);
linklist *list1,*list2,*list3;
list1 = CreateList_End();
list2 = CreateList_End();
list3 = SumTwoList(list1,list2);
ShowLinklist(list3);
}
void ShowLinklist(linklist*h)
{
linklist *p;
p = h ;
while(p!=NULL)
{
printf("%d",p->val);
p = p->next;
}
printf("\n");
}
linklist * SumTwoList(linklist*l1,linklist*l2)
{
ShowLinklist(l1);
ShowLinklist(l2);
typedef struct ListNode linklist;
linklist *head,*p,*e,*p1,*p2;
p1 = l1;
p2 = l2;
int ch;
head = NULL;
e = NULL;
int flag = 0;
while(p1!=NULL&&p2!=NULL)
{
p = (linklist*)malloc(sizeof(linklist));
ch = p1->val+p2->val+flag;
flag = 0;
if(ch >9){
ch = ch-10;
flag = 1;
}
p->val = ch;
if(head==NULL)
{
head = p;
}
else
{
e->next = p;
}
e = p;
p1 = p1->next;
p2 = p2->next;
}
while(p1!=NULL)
{
p = (linklist*)malloc(sizeof(linklist));
ch = p1->val+flag;
flag = 0;
if(ch >9){
ch = ch-10;
flag = 1;
}
p->val = ch;
if(head==NULL)
{
head = p;
}
else
{
e->next = p;
}
e = p;
p1 = p1->next;
}
while(p2!=NULL)
{
p = (linklist*)malloc(sizeof(linklist));
ch = p2->val+flag;
flag = 0;
if(ch >9){
ch = ch-10;
flag = 1;
}
p->val = ch;
if(head==NULL)
{
head = p;
}
else
{
e->next = p;
}
e = p;
p2 = p2->next;
}
if(flag ==1)
{
p = (linklist*)malloc(sizeof(linklist));
ch = 1;
flag = 0;
p->val = ch;
if(head==NULL)
{
head = p;
}
else
{
e->next = p;
}
e = p;
}
if (e != NULL)
{
e->next =NULL;
}
return head;
}
linklist * CreateList_Front()
{
linklist *head,*p;
char ch;
head = NULL;
ch = getchar();
while(ch!='#')
{
p = (linklist*)malloc(sizeof(linklist));
p->val = ch-48;
p->next = head;
head = p;
ch = getchar();
}
return head;
}
linklist * CreateList_End()
{
linklist *head,*p,*e;
char ch;
head = NULL;
e = NULL;
ch = getchar();
while(ch!='#')
{
if(ch<73&&ch>47)
{
p = (linklist*)malloc(sizeof(linklist));
p->val = ch-48;
if(head==NULL)
{
head = p;
}
else
{
e->next = p;
}
e = p;
}
ch = getchar();
}
if (e != NULL)
{
e->next =NULL;
}
return head;
}
linklist * CreateList_End_F_N()
{
linklist *head,*p,*e;
char ch;
head = (linklist*)malloc(sizeof(linklist));
head->val = 'S';
e = head;
ch = getchar();
while(ch != '#')
{
p = (linklist*)malloc(sizeof(linklist));
p->val=ch;
e->next = p;
e = p;
ch = getchar();
}
e->next = NULL;
return head;
}