Add Two Numbers

題目描述

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.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

簡(jiǎn)單描述：兩個(gè)鏈表按順序相加，大于10的取10的余數(shù)(%10),向下位進(jìn)1。

注意點(diǎn)：當(dāng)最后一個(gè)節(jié)點(diǎn)的和大于等于10時(shí)，需要增加一個(gè)節(jié)點(diǎn)。

C語(yǔ)言

#include<stdio.h>
#include<malloc.h>

struct ListNode{
    int val;
    struct ListNode *next;
 };
 


//創(chuàng)建NULL節(jié)點(diǎn) 
struct ListNode* newNode(int a){
    struct ListNode* newListNode = malloc(sizeof(struct ListNode));
    if(newListNode==NULL){
        return NULL; 
    }
    newListNode->val = a;
    newListNode->next = NULL;
    return newListNode; 
}

//創(chuàng)建 指定長(zhǎng)度和數(shù)據(jù)的鏈表 
struct ListNode* createListNode(long array[],int n){
    int i;
    struct ListNode *head,*p;
    head = p = newNode(array[0]);
    
    for(i=1;i<n;i++){
        p->next = newNode(array[i]);
        p = p->next;
    }
    return head;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode * p1,*p2;
    p1 = l1;
    p2 = l2;
    
    struct ListNode* head;
    head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* p3 = head;
  
    int  t =0;
    
    while(p1!=NULL || p2!=NULL){

        int a1 = p1!=NULL? p1->val : 0;
        int a2 = p2!=NULL? p2->val : 0;
        int sum = a1+a2+t;
        t = sum/10;
 
        p3->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        p3 = p3->next;
        p3->val = sum%10;
        
        if(p1!=NULL){
            p1 = p1->next;
        }
        if(p2!=NULL){
            p2 = p2->next; 
        }
    }
    
    if(t>0){
        p3->next = (struct ListNode*)malloc(sizeof(struct ListNode)); 
        p3 = p3->next;
        p3->val = t;
    }
    p3->next=NULL;
    return head->next;
}

//測(cè)試
int main(){
    struct ListNode *l1,*l2;
//  int a1[] = {2,4,3};
//  int a2[] = {5,6,4};
//  l1 = createListNode(a1,3);
//  l2 = createListNode(a2,3);
//  long a1[] = {9};
//  long a2[] = {1,9,9,9,9,9,9,9,9,9};
//  l1 = createListNode(a1,1);
//  l2 = createListNode(a2,10);
    long a1[] = {5};
    long a2[] = {5};
    l1 = createListNode(a1,1);
    l2 = createListNode(a2,1);
    
    struct ListNode *p = addTwoNumbers(l1,l2); 
    while(p!=NULL){
        printf("->%d",p->val);
        p = p->next;
    }
    return 0;
}

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(max(m,n))， 只有一個(gè)while語(yǔ)句，傳入的2個(gè)鏈表的最大長(zhǎng)度決定循環(huán)的次數(shù)。

空間復(fù)雜度：O(max(m,n))，傳入的2個(gè)鏈表的最大空間決定新建鏈表的最大空間，如果最后節(jié)點(diǎn)和大于等于10，空間復(fù)雜度為O(max(m,n))+1。

Java實(shí)現(xiàn)

public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { 
            val = x;
      }
 }

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head= new ListNode(0);
    ListNode p = l1, q = l2, curr = head;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return head.next;
}

Java版和C語(yǔ)言版基本一樣。