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

我认为这是超出背景的东西，但对于最初发布此问题的人来说可能是非常好的表现。

所以这是一个建议：

而不是将每个节点用作数字的单个数字，使用每个节点存储一个大数字（接近整数的大小），如果您选择在每个节点中存储的最高数量是 x（你的情况9）然后你可以查看你的号码作为表示 base x+1。 其中每个数字是0到x之间的数字。

这将为您带来显着的性能提升，因为算法将在O（log n）时间内运行，并且在您的情况下需要与O（n）相同的节点数，n是两个加数中较大者的小数位数。

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

例如，如果您的号码是1234567890987654321，并且您想将其存储在链接列表中，选择基数为10 ^ 8，那么您的表示应如下所示：

87654321-> 4567890 - > 123（little endian）

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

此代码假定：

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

它使用递归来传播总和并携带每个数字，并从左到右求和。列表永远不会反转 - 总和从左到右执行，并且进位在递归堆栈中传播。它可以在迭代解决方案中展开，但我不会担心。

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;
    }
}

这是一个伪代码。

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;
}

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

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;
}
}

// 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;
}

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

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

3.现在调用以下递归函数并将标志设置为零：

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.现在需要在目标列表的开头添加剩余的n-m个节点，可以使用循环直接完成。请注意，对于循环中的最后一个元素，您需要添加add（）函数返回的标志，因为可能存在进位。

如果您的问题没有使用递归：

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

2.遍历两个列表以及目标列表（后退一步）。如果找到两个节点之和大于10，则将目标列表中的值设置为“1”。

3.通过上述步骤，您可以随身携带。现在在另一个传递中，只需添加模数为10的两个节点，并将此值添加到目标列表的相应节点中。

不使用堆栈..... 只需将链接列表的内容存储在数组中并执行添加，然后再将其添加到链接列表中

代码：

#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;
}  

我们可以使用递归来添加它们。假设问题定义如下：我们有列表 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;
    }

Input : List a , List b
Output : List c

这里的大多数方法都需要额外的空间用于List a和List b。这可以删除。

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

/* 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;
}