leetcode

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

算法思想:

  1. 链表的遍历操作.
  2. 进位操作,设置一个标志位,默认为0,大于10则进位,算完之后标志位清零.
  3. 注意链表的长度,有的时候某一个链表先遍历完,需要继续遍历另外一个.
  4. 合成的链表按照尾插法的形式建立.
  /*
问题描述:
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;
}

上一篇下一篇

猜你喜欢

热点阅读