添加两个表示为链接列表的大数字而不反转链接列表

Question

假设您有两个大数字表示为链接列表，那么如何添加它们并将结果存储在单独的链接列表中。 如

a = 2 -> 1 -> 7 
b = 3 -> 4 
result = 2 -> 5 -> 1 

你能无需反转链表

Answer 1

它们添加/ *扰流板：只是普通的递归会做*/

#include <stdio.h> 

struct list { 
    struct list *next; 
    unsigned value; 
    }; 
struct list a[] = { {NULL, 2} , {NULL, 1} , {NULL, 7} }; 
struct list b[] = { {NULL, 3} , {NULL, 4} }; 

unsigned recurse(unsigned * target, struct list *lp); 
unsigned recurse(unsigned * target, struct list *lp) 
{ 
    unsigned fact; 
    if (!lp) return 1; 
    fact = recurse (target, lp->next); 

    *target += fact * lp->value; 
    return 10*fact; 
} 

int main (void) 
{ 
    unsigned result=0; 

    /* set up the links */ 
    a[0].next = &a[1]; 
    a[1].next = &a[2]; 
    b[0].next = &b[1]; 

    (void) recurse (&result, a); 
    (void) recurse (&result, b); 

    printf("Result = %u\n" , result); 

return 0; 
} 

Answer 2

这里是一个伪代码。

list *add (list *l1, list *l2) 
{ 
    node *l3, l3_old; 

    while (l1 != NULL) 
    { 
    stack1.push (l1); 
    l1 = l1->next; 
    } 
    while (l2 != NULL) 
    { 
    stack2.push (l2); 
    l2 = l2->next; 
    } 

    l3_old = NULL; 
    while (!stack1.isempty() && !stack2.isempty()) // at least one stack is not empty 
    { 
    l3 = get_new_node(); 
    l1 = stack1.pop(); 
    l2 = stack2.pop(); 
    l3->val = l1->val + l2->val; 
    if (l3_old != NULL) 
    { 
     l3->val = l3->val + (int)l3_old/10; 
     l3_old->val %= 10; 
    } 
    l3->next = l3_old; 
    l3_old = l3; 
    } 
    while (!stack1.isempty()) 
    { 
    l1 = stack1.pop(); 
    l3 = get_new_node(); 
    l3->val = l1->val + (int)l3_old->val/10; 
    l3_old->val %= 10; 
    l3->next = l3_old; 
    l3_old = l3; 
    } 
    while (!stack2.isempty()) 
    { 
    l2 = stack2.pop(); 
    l3 = get_new_node(); 
    l3->val = l2->val + (int)l3_old->val/10; 
    l3_old->val %= 10; 
    l3->next = l3_old; 
    l3_old = l3; 
    } 
    return l3; 
} 

Answer 3

这是我在大约O（max（len（a），len（b）））运行的Java中的hacky尝试。我用一个非常简单的单链表实现提供了一个完整的示例。这里很晚，所以代码没有我想要的那么好 - 对不起！

此代码假定：

• 即列表的长度是已知的
• 单链表
• 整数数据

它使用递归传播的总和和进位处理为每个数字，并从左到右总结。这些列表永远不会颠倒 - 总是从左到右执行，并进行递归堆栈传播。它可以在迭代解决方案中展开，但我不担心这一点。

public class LinkedListSum { 
    static class LLNode { 
     int value; 
     LLNode next; 
     public LLNode(int value){ 
      this.value = value; 
     } 
     public int length(){ 
      LLNode node = this; 
      int count = 0; 
      do { 
       count++; 
      } while((node = node.next) != null); 
      return count; 
     } 
     public List<Integer> toList(){ 
      List<Integer> res = new ArrayList<Integer>(); 
      LLNode node = this; 
      while(node != null){ 
       res.add(node.value); 
       node = node.next; 
      } 
      return res; 
     } 
    } 

    public static void main(String[] argc){ 
     LLNode list_a = fromArray(new int[]{4,7,4,7}); 
     LLNode list_b = fromArray(new int[]{5,3,7,4,7,4}); 
     System.out.println("Sum: " + sum(list_a, list_b).toList()); 
    } 

    private static LLNode fromArray(int[] arr){ 
     LLNode res = new LLNode(0); 
     LLNode current = res; 
     for(int i = 0; i < arr.length; i++){ 
      LLNode node = new LLNode(arr[i]); 
      current.next = node; 
      current = node; 
     } 
     return res.next; 
    } 

    private static LLNode sum(LLNode list_1, LLNode list_2){ 
     LLNode longer; 
     LLNode shorter; 
     if(list_1.length() >= list_2.length()){ 
      longer = list_1; 
      shorter = list_2; 
     } else { 
      longer = list_2; 
      shorter = list_1; 
     } 

     // Pad short to same length as long 
     int diff = longer.length() - shorter.length(); 
     for(int i = 0; i < diff; i++){ 
      LLNode temp = new LLNode(0); 
      temp.next = shorter; 
      shorter = temp; 
     } 

     System.out.println("Longer: " + longer.toList()); 
     System.out.println("Shorter: " + shorter.toList()); 

     return sum_same_length(new LLNode(0), null, longer, shorter); 
    } 

    private static LLNode sum_same_length(LLNode current, LLNode previous, LLNode longerList, LLNode shorterList){ 
     LLNode result = current; 
     if(longerList == null){ 
      previous.next = null; 
      return result; 
     } 

     int sum = longerList.value + shorterList.value; 
     int first_value = sum % 10; 
     int first_carry = sum/10; 
     current.value = first_value; 

     // Propagate the carry backwards - increase next multiple of 10 if necessary 
     LLNode root = propagateCarry(current,previous,first_carry); 

     current.next = new LLNode(0); 
     sum_same_length(current.next, current, longerList.next, shorterList.next); 

     // Propagate the carry backwards - increase next multiple of 10 if necessary: 
     // The current value could have been increased during the recursive call 
     int second_value = current.value % 10; 
     int second_carry = current.value/10; 
     current.value = second_value; 

     root = propagateCarry(current,previous,second_carry); 
     if(root != null) result = root; 

     return result; 
    } 

    // Returns the new root of the linked list if one had to be added (due to carry) 
    private static LLNode propagateCarry(LLNode current, LLNode previous, int carry){ 
     LLNode result = null; 
     if(carry != 0){ 
      if(previous != null){ 
       previous.value += carry; 
      } else { 
       LLNode first = new LLNode(carry); 
       first.next = current; 
       result = first; 
      } 
     } 
     return result; 
    } 
} 

Answer 4

/* this baby does not reverse the list 
** , it does use recursion, and it uses a scratch array */ 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

struct list { 
    struct list *next; 
    unsigned value; 
    }; 

unsigned recurse(char target[], struct list *lp); 
struct list * grab (char buff[], size_t len); 

unsigned recurse(char target[], struct list *lp) 
{ 
    unsigned pos; 
    if (!lp) return 0; 
    pos = recurse (target, lp->next); 
    /* We should do a bounds check target[] here */ 
    target[pos] += lp->value; 
    if (target[pos] >= 10) { 
     target[pos+1] += target[pos]/10; 
     target[pos] %= 10; 
     } 
    return 1+pos; 
} 

struct list * grab (char *buff, size_t len) 
{ 
size_t idx; 
struct list *ret, **hnd; 

    /* Skip prefix of all zeros. */ 
    for (idx=len; idx--;) { 
     if (buff [idx]) break; 
     } 
    if (idx >= len) return NULL; 

    /* Build the result chain. Buffer has it's LSB at index=0, 
    ** but we just found the MSB at index=idx. 
    */ 
    ret = NULL; hnd = &ret; 
    do { 
     *hnd = malloc (sizeof **hnd); 
     (*hnd)->value = buff[idx]; 
     (*hnd)->next = NULL; 
     hnd = &(*hnd)->next; 
     } while (idx--); 

return ret; 
} 

int main (void) 
{ 
    char array[10]; 
    struct list a[] = { {NULL, 2} , {NULL, 1} , {NULL, 7} }; 
    struct list b[] =    { {NULL, 3} , {NULL, 4} }; 
    struct list *result; 

    a[0].next = &a[1]; a[1].next = &a[2]; 
    b[0].next = &b[1]; 

    memset(array, 0 , sizeof array); 
    (void) recurse (array, a); 
    (void) recurse (array, b); 
    result = grab (array, sizeof array); 

    for (; result; result = result->next) { 
     printf("-> %u" , result->value); 
     } 
    printf("\n"); 

return 0; 
} 

Answer 5

我觉得这件事情超出了上下文，但是可以是谁最初发布此问题的人非常绩效激励。

所以这里有一个建议：

，而不是使用每个节点的数量的一个数字，请在每个节点存储了大量的（接近整数的大小），如果你选择了最大可能的数目要在每个节点中储存x（您的情况9），那么您可以在base x+1中查看您的电话号码。 其中每个数字是介于0和x之间的数字。

这将使您获得显着的性能增益，因为该算法在O（log n）时间内运行，并且需要的节点数与O（n）相同，n是较大的小数位数的两个加数。

通常为了简化算法，您可以选择10的幂作为适合整数范围的基数。

例如，如果你的电话号码是1234567890987654321，你想将其存储在链接列表中选择基本是10^8那么你的表现应该是这样的：

87654321-> 4567890 - > 123（小端）

Answer 6

最终版本（无链表反转，没有递归）：

#include <stdio.h> 
#include <stdlib.h> 

struct list { 
     struct list *nxt; 
     unsigned val; 
     }; 

struct list *sumlist(struct list *l, struct list *r); 
int difflen(struct list *l, struct list *r); 

struct list *sumlist(struct list *l, struct list *r) 
{ 
int carry,diff; 
struct list *result= NULL, **pp = &result; 

     /* If the lists have different lengths, 
     ** the sum will start with the prefix of the longest list 
     */ 
for (diff = difflen(l, r); diff; diff += (diff > 0) ? -1 : 1) { 
     *pp = malloc (sizeof **pp) ; 
     (*pp)->nxt = NULL; 
     if (diff > 0) { (*pp)->val = l->val; l= l->nxt; } 
     else { (*pp)->val = r->val; r= r->nxt; } 
     pp = &(*pp)->nxt ; 
     } 

     /* Do the summing. 
     ** whenever the sum is ten or larger we increment a carry counter 
     */ 
for (carry=0; l && r; l=l->nxt, r=r->nxt) { 
     *pp = malloc (sizeof **pp) ; 
     (*pp)->nxt = NULL; 
     (*pp)->val = l->val + r->val; 
     if ((*pp)->val > 9) carry++; 
     pp = &(*pp)->nxt ; 
     } 

     /* While there are any carries, we will need to propagate them. 
     ** Because we cannot reverse the list (or walk it backward), 
     ** this has to be done iteratively. 
     ** Special case: if the first digit needs a carry, 
     ** we have to insert a node in front of it 
     */ 
for (diff =0 ;carry; carry = diff) { 
     struct list *tmp; 
     if (result && result->val > 9) { 
       tmp = malloc(sizeof *tmp); 
       tmp->nxt = result; 
       tmp->val = 0; 
       result = tmp; 
       } 
     diff=0; 
     for (tmp=result; tmp ; tmp= tmp->nxt) { 
       if (tmp->nxt && tmp->nxt->val > 9) { 
        tmp->val += tmp->nxt->val/10; 
        tmp->nxt->val %= 10; } 
       if (tmp->val > 9) diff++; 
       } 
     } 
return result; 
} 

int difflen(struct list *l, struct list *r) 
{ 
int diff; 

for (diff=0; l || r; l = (l)?l->nxt:l, r = (r)?r->nxt:r) { 
     if (l && r) continue; 
     if (l) diff++; else diff--; 
     } 
return diff; 
} 

int main (void) 
{ 
     struct list one[] = { {one+1, 2} , {one+2, 6} , {NULL, 7} }; 
     struct list two[] = { {two+1, 7} , {two+2, 3} , {NULL, 4} }; 
     struct list *result; 

     result = sumlist(one, two); 

     for (; result; result = result->nxt) { 
       printf("-> %u" , result->val); 
       } 
     printf(";\n"); 

return 0; 
} 

Answer 7

这里是我的尝试，使用两个链表和返回的总和使用递归的新列表。

public class SumList { 

int[] a1= {7,3,2,8}; 
int[] a2= {4,6,8,4}; 
LinkedList l1= new LinkedList(a1); 
LinkedList l2= new LinkedList(a2); 
Node num1= l1.createList(); 
Node num2= l2.createList(); 
Node result; 

public static void main(String[] args) { 
    SumList sl= new SumList(); 
    int c= sl.sum(sl.num1, sl.num2); 
    if(c>0) { 
     Node temp= new Node(c); 
     temp.next= sl.result; 
     sl.result= temp; 
    } 

    while(sl.result != null){ 
     System.out.print(sl.result.data); 
     sl.result= sl.result.next; 
    } 
} 

int sum(Node n1, Node n2) { 
    if(n1==null || n2==null) 
     return 0; 
    int a1= this.getSize(n1); 
    int a2= this.getSize(n2); 
    int carry, s= 0; 
    if(a1>a2) { 
     carry= sum(n1.next, n2); 
     s= n1.data+carry; 
    } 
    else if(a2>a1) { 
     carry= sum(n1, n2.next); 
     s= n2.data+carry; 
    } 
    else { 
     carry= sum(n1.next, n2.next); 
     s= n1.data+n2.data+carry; 
    } 
    carry= s/10; 
    s=s%10; 

    Node temp= new Node(s); 
    temp.next= result; 
    result= temp; 

    return carry; 
} 

int getSize(Node n) { 
    int count =0; 
    while(n!=null) { 
     n=n.next; 
     count++; 
    } 
    return count; 
} 
} 

Answer 8

// A recursive program to add two linked lists 

#include <stdio.h> 
#include <stdlib.h> 

// A linked List Node 
struct node 
{ 
int data; 
struct node* next; 
}; 

typedef struct node node; 

/* A utility function to insert a node at the beginning of linked list */ 
void push(struct node** head_ref, int new_data) 
{ 
/* allocate node */ 
struct node* new_node = (struct node*) malloc(sizeof(struct node)); 

/* put in the data */ 
new_node->data = new_data; 

/* link the old list off the new node */ 
new_node->next = (*head_ref); 

/* move the head to point to the new node */ 
(*head_ref) = new_node; 
} 

/* A utility function to print linked list */ 
void printList(struct node *node) 
{ 
while (node != NULL) 
{ 
    printf("%d ", node->data); 
    node = node->next; 
} 
printf("\n"); 
} 

// A utility function to swap two pointers 
void swapPointer(node** a, node** b) 
{ 
node* t = *a; 
*a = *b; 
*b = t; 
} 

/* A utility function to get size of linked list */ 
int getSize(struct node *node) 
{ 
int size = 0; 
while (node != NULL) 
{ 
    node = node->next; 
    size++; 
} 
return size; 
} 

// Adds two linked lists of same size represented by head1 and head2 and returns 
// head of the resultant linked list. Carry is propagated while returning from 
// the recursion 
node* addSameSize(node* head1, node* head2, int* carry) 
{ 
// Since the function assumes linked lists are of same size, 
// check any of the two head pointers 
if (head1 == NULL) 
    return NULL; 

int sum; 

// Allocate memory for sum node of current two nodes 
node* result = (node *)malloc(sizeof(node)); 

// Recursively add remaining nodes and get the carry 
result->next = addSameSize(head1->next, head2->next, carry); 

// add digits of current nodes and propagated carry 
sum = head1->data + head2->data + *carry; 
*carry = sum/10; 
sum = sum % 10; 

// Assigne the sum to current node of resultant list 
result->data = sum; 

return result; 
} 

// This function is called after the smaller list is added to the bigger 
// lists's sublist of same size. Once the right sublist is added, the carry 
// must be added toe left side of larger list to get the final result. 
void addCarryToRemaining(node* head1, node* cur, int* carry, node** result) 
{ 
int sum; 

// If diff. number of nodes are not traversed, add carry 
if (head1 != cur) 
{ 
    addCarryToRemaining(head1->next, cur, carry, result); 

    sum = head1->data + *carry; 
    *carry = sum/10; 
    sum %= 10; 

    // add this node to the front of the result 
    push(result, sum); 
    } 
} 

// The main function that adds two linked lists represented by head1 and head2. 
// The sum of two lists is stored in a list referred by result 
void addList(node* head1, node* head2, node** result) 
{ 
node *cur; 

// first list is empty 
if (head1 == NULL) 
{ 
    *result = head2; 
    return; 
} 

// second list is empty 
else if (head2 == NULL) 
{ 
    *result = head1; 
    return; 
} 

int size1 = getSize(head1); 
int size2 = getSize(head2) ; 

int carry = 0; 

// Add same size lists 
if (size1 == size2) 
    *result = addSameSize(head1, head2, &carry); 

else 
{ 
    int diff = abs(size1 - size2); 

    // First list should always be larger than second list. 
    // If not, swap pointers 
    if (size1 < size2) 
     swapPointer(&head1, &head2); 

    // move diff. number of nodes in first list 
    for (cur = head1; diff--; cur = cur->next); 

    // get addition of same size lists 
    *result = addSameSize(cur, head2, &carry); 

    // get addition of remaining first list and carry 
    addCarryToRemaining(head1, cur, &carry, result); 
} 

// if some carry is still there, add a new node to the fron of 
// the result list. e.g. 999 and 87 
if (carry) 
    push(result, carry); 
} 

// Driver program to test above functions 
int main() 
{ 
node *head1 = NULL, *head2 = NULL, *result = NULL; 

int arr1[] = {9, 9, 9}; 
int arr2[] = {1, 8}; 

int size1 = sizeof(arr1)/sizeof(arr1[0]); 
int size2 = sizeof(arr2)/sizeof(arr2[0]); 

// Create first list as 9->9->9 
int i; 
for (i = size1-1; i >= 0; --i) 
    push(&head1, arr1[i]); 

// Create second list as 1->8 
for (i = size2-1; i >= 0; --i) 
    push(&head2, arr2[i]); 

addList(head1, head2, &result); 

printList(result); 

return 0; 
} 

Answer 9

1.首先遍历两个列表，找到两个列表的长度（设m，n为长度）。

2.遍历较长列表中的n-m个节点，并将“prt1”设置为当前节点，将“ptr2”设置为另一个列表的开头。

3.Now调用具有标志设置为零以下递归函数：

void add(node* ptr1,node* ptr2){ 
    if(ptr1==NULL) 
     return; 

    add(ptr1->next,ptr2->next); 
    insertAtBegin(ptr1->data+ptr2->data+flag); 
    flag=(ptr1->data+ptr2->data)%10; 
} 

4.Now你需要在你的目标列表的开头加入剩余纳米节点，你可以直接使用它做一个循环。请注意，对于循环中的最后一个元素，您需要添加由add（）函数返回的标志，因为可能会有进位。

如果你的问题是不使用递归：

1.Repeat前两步，然后创建目标列表中的每个元素initalising“0”（确保列表的长度为准） 。

2.遍历两个列表以及目标列表（后面一步）。如果发现两个节点的总和大于10，请将目标列表中的值设置为'1'。

3.通过上述步骤，您照顾了携带。现在再次添加两个节点模10，并将此值添加到目标列表的相应节点中。

Answer 10

伪代码：
步骤1.遍历链接列表，并在两个不同的堆栈
步骤2.弹出从顶部元件两者堆叠
步骤3.添加元素（+来自先前任何携带推元件加法）和存储在临时的进位可变
步骤4.创建与和一个节点，并把它插入到结果列表

Answer 11

的开始，而无需使用堆..... 简单地存储链路的内容在数组中列出并执行加法，然后再将其添加到链接列表

代码：

#include<stdio.h> 
#include<malloc.h> 
typedef struct node 
{ 
    int value; 
    struct node *next; 
}node; 

int main() 
{ 
    printf("\nEnter the number 1 : "); 
    int ch; 
    node *p=NULL; 
    node *k=NULL; 
    printf("\nEnter the number of digit : "); 
    scanf("%d",&ch); 
    int i=0; 
    while(ch!=i) 
    { 
     i++; 
     node *q=NULL; 
     int a=0; 
     q=(node *)malloc(sizeof(node)); 
     printf("\nEnter value : "); 
     scanf("%d",&a); 
     q->value=a; 
     if(p==NULL) 
     { 
      q->next=NULL; 
      p=q; 
      k=p; 
     } 
     else 
     { 
      q->next=NULL; 
      p->next=q; 
      p=q;  
     } 
    } 
    printf("\nEnter the number 2 : "); 
    int ch1; 
    node *p1=NULL; 
    node *k1=NULL; 
    int i1=0; 
    printf("\nEnter the number of digit : "); 
    scanf("%d",&ch1); 
    while(ch1!=i1) 
    { 
     i1++; 
     node *q1=NULL; 
     int a1=0; 
     q1=(node *)malloc(sizeof(node)); 
     printf("\nEnter value : "); 
     scanf("%d",&a1); 
     q1->value=a1; 
     if(p1==NULL) 
     { 
      q1->next=NULL; 
      p1=q1; 
      k1=p1; 
     } 
     else 
     { 
      q1->next=NULL; 
      p1->next=q1; 
      p1=q1; 
     } 
    } 
    printf("\n\t"); 
    int arr1[100]; 
    int arr1_ptr=0; 
    while(k != NULL) 
    { 
     printf("%d\t",k->value); 
     arr1[arr1_ptr++]=k->value; 
     k=k->next; 

    } 
    printf("\n\t"); 
    int arr2[100]; 
    int arr2_ptr=0; 

    while(k1 != NULL) 
    { 
     printf("%d\t",k1->value); 
     arr2[arr2_ptr++]=k1->value; 
     k1=k1->next; 

    } 
//addition logic ...  
    int result[100]={0}; 
    int result_ptr=0; 
    int loop_ptr=0; 
    int carry=0; 
    arr1_ptr--; 
    arr2_ptr--; 
    if(arr1_ptr>arr2_ptr) 
     loop_ptr=arr1_ptr+1; 
    else 
     loop_ptr=arr2_ptr+1;  
    for(int i = loop_ptr ; i >= 0;i--) 
    { 
     if(arr1_ptr >= 0 && arr2_ptr >= 0) 
     { 

      if((arr1[arr1_ptr] + arr2[arr2_ptr] + carry) > 9) 
      { 
       result[i]=((arr1[arr1_ptr] + arr2[arr2_ptr]+carry) % 10); 
       carry = ((arr1[arr1_ptr--] + arr2[arr2_ptr--]+carry)/10) ; 
      } 
      else 
      { 
       result[i]=(arr1[arr1_ptr--] + arr2[arr2_ptr--] + carry ); 
       carry = 0 ; 
      } 
     } 
     else if(!(arr1_ptr < 0) || !(arr2_ptr < 0)) 
     { 
      if(arr1_ptr < 0) 
       result[i]=arr2[arr2_ptr--]+carry; 
      else 
       result[i]=arr1[arr1_ptr--]+carry;  
     } 
     else 
      result[i]=carry; 
    } 
    /*printf("\n"); 
    for(int i=0;i<loop_ptr+1;i++) 
     printf("%d\t",result[i]); 
    */ 
    node *k2=NULL,*p2=NULL; 
    for(int i=0;i<loop_ptr+1;i++) 
    { 

     node *q2=NULL; 
     q2=(node *)malloc(sizeof(node)); 
     q2->value=result[i]; 
     if(p2==NULL) 
     { 
      q2->next=NULL; 
      p2=q2; 
      k2=p2; 
     } 
     else 
     { 
      q2->next=NULL; 
      p2->next=q2; 
      p2=q2; 
     } 


    } 
    printf("\n"); 
    while(k2 != NULL) 
    { 
     printf("%d\t",k2->value); 
     k2=k2->next; 
    } 
    return 0; 
} 

Answer 12

我们可以通过使用递归添加。假设问题定义如下：我们有l1和l2的列表，我们希望通过将结果存储在l1中来添加它们。为了简单起见，假定两个列表具有相同的长度（代码可以很容易地修改以适应不同的长度）。这是我工作的Java解决方案：

private static ListNode add(ListNode l1, ListNode l2){ 
     if(l1 == null) 
      return l2; 
     if(l2 == null) 
      return l1; 
     int[] carry = new int[1]; 
     add(l1, l2, carry); 
     if(carry[0] != 0){ 
      ListNode newHead = new ListNode(carry[0]); 
      newHead.next = l1; 
      return newHead; 
     } 
     return l1; 
    } 
    private static void add(ListNode l1, ListNode l2, int[] carry) { 
     if(l1.next == null && l2.next == null){ 
      carry[0] = l1.val + l2.val; 
      l1.val = carry[0]%10; 
      carry[0] /= 10; 
      return; 
     } 
     add(l1.next, l2.next, carry); 
     carry[0] += l1.val + l2.val; 
     l1.val = carry[0]%10; 
     carry[0] /= 10; 
    } 

Answer 13

在java中我会做这样

public class LLSum { 
public static void main(String[] args) { 
    LinkedList<Integer> ll1 = new LinkedList<Integer>(); 
    LinkedList<Integer> ll2 = new LinkedList<Integer>(); 

    ll1.add(7); 
    ll1.add(5); 
    ll1.add(9); 
    ll1.add(4); 
    ll1.add(6); 

    ll2.add(8); 
    ll2.add(4); 

    System.out.println(addLists(ll1,ll2)); 
} 
public static LinkedList<Integer> addLists(LinkedList<Integer> ll1, LinkedList<Integer> ll2){ 
    LinkedList<Integer> finalList = null; 

    int num1 = makeNum(ll1); 
    int num2 = makeNum(ll2); 

    finalList = makeList(num1+num2); 
    return finalList; 
} 
private static LinkedList<Integer> makeList(int num) { 
    LinkedList<Integer> newList = new LinkedList<Integer>(); 

    int temp=1; 
    while(num!=0){ 
     temp = num%10; 
     newList.add(temp); 
     num = num/10; 
    } 
    return newList; 
} 
private static int makeNum(LinkedList<Integer> ll) { 
    int finalNum = 0; 
    for(int i=0;i<ll.size();i++){ 
     finalNum += ll.get(i) * Math.pow(10,i); 
    } 
    return finalNum; 
    } 
} 

Answer 14

Input : List a , List b 
Output : List c 

这里大部分方法需要对列表中的一个和名单B额外的空间。这可以被删除。

1. 反向列表a和列表b使得它们以相反的顺序表示（即，尾部作为头部，所有链接反转）并具有恒定的空间O（1）。
2. 然后通过同时遍历它们并保持进位来有效地添加列表。如果需要的话

Answer 15

这里

逆向列表A和列表b为我第一次尝试：

public class addTwo { 
public static void main(String args[]){ 
    LinkedListNode m =new LinkedListNode(3); 
    LinkedListNode n = new LinkedListNode(5); 
    m.appendNew(1); 
    m.appendNew(5); 
    m.appendNew(5); 
    n.appendNew(9); 
    n.appendNew(2); 
    n.appendNew(5); 
    n.appendNew(9); 
    n.appendNew(9); 
    m.print(); 
    n.print(); 
    LinkedListNode add=addTwo(m,n); 
    add.print(); 

} 

static LinkedListNode addTwo(LinkedListNode m,LinkedListNode n){ 
    LinkedListNode result; 
    boolean flag =false; 
    int num; 
    num=m.data+n.data+(flag?1:0); 
    flag=false; 
    if(num>9){ 
     flag=true; 
    } 
    result = new LinkedListNode(num%10); 
    while(m.link!=null && n.link!=null){ 
     m=m.link; 
     n=n.link; 
     num=m.data+n.data+(flag?1:0); 
     flag=false; 
     if(num>9){ 
      flag=true; 
     } 
     result.appendNew(num%10); 
    } 

    if(m.link==null && n.link==null){ 
     if(flag) 
      result.appendNew(1); 
     flag=false; 
    }else if(m.link!=null){ 
     while(m.link !=null){ 
      m=m.link; 
      num=m.data; 
      num=m.data+(flag?1:0); 
      flag=false; 
      if(num>9){ 
       flag=true; 
      } 
      result.appendNew(num%10); 
     } 
    }else{ 
     while(n.link !=null){ 
      n=n.link; 
      num=n.data; 
      num=n.data+(flag?1:0); 
      flag=false; 
      if(num>9){ 
       flag=true; 
      } 
      result.appendNew(num%10); 
     } 
    } 
    if(flag){ 
     result.appendNew(1); 
    } 

    return result; 
} 

class LinkedListNode { 
public int data; 
public LinkedListNode link; 
public LinkedListNode(){System.out.println(this+":"+this.link+":"+this.data);} 
public LinkedListNode(int data){ 
    this.data=data; 
} 
void appendNew(int data){ 
    if(this==null){ 
     System.out.println("this is null"); 
     LinkedListNode newNode = new LinkedListNode(data); 
    } 
    LinkedListNode newNode = new LinkedListNode(data); 
    LinkedListNode prev =this; 
    while(prev.link!=null){ 
     prev = prev.link; 
    } 
    prev.link=newNode; 
} 
void print(){ 
    LinkedListNode n=this; 
    while(n.link!=null){ 
     System.out.print(n.data +"->"); 
     n = n.link; 
    } 
    System.out.println(n.data); 
} 
} 

结果是：

3-> 1-> 5-> 5

5-> 9-> 2-> 5-> 9-> 9

8-> 0-> 8-> 0-> 0-> 0-> 1