Additionner deux grands nombres représentés sous forme de listes chaînées sans inverser les listes chaînées.

Question

Supposons que vous ayez 2 grands nombres représentés sous forme de listes chaînées, comment les additionner et stocker le résultat dans une liste chaînée séparée. Par exemple,

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

Pouvez-vous les ajouter sans inverser les listes liées

Answer 1

// 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 2

Tout d'abord, parcourez les deux listes et trouvez les longueurs des deux listes (m et n étant les longueurs).

2. parcourir n-m noeuds dans la liste la plus longue et placer 'prt1' au noeud actuel et 'ptr2' au début de l'autre liste.

Appelez maintenant la fonction récursive suivante avec le drapeau à zéro :

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

Maintenant, vous devez ajouter les n-m nœuds restants au début de votre liste de cibles, vous pouvez le faire directement en utilisant une boucle. Notez que pour le dernier élément de la boucle, vous devez ajouter le drapeau renvoyé par la fonction add() car il peut y avoir un report.

Si votre question est sans utiliser la récursion :

Répétez les deux premières étapes, puis créez votre liste cible en initialisant tous les éléments par '0' (assurez-vous que la longueur de la liste est exacte).

Traversez les deux listes avec votre liste cible (un pas en arrière). Si vous trouvez que la somme de deux nœuds est supérieure à 10, mettez la valeur '1' dans la liste cible.

3) Avec l'étape ci-dessus, vous avez pris soin du transport. Maintenant, dans une autre passe, il suffit d'ajouter les deux nœuds modulo 10 et d'ajouter cette valeur dans le nœud correspondant de la liste cible.

Answer 3

Sans utiliser la pile ..... il suffit de stocker le contenu de la liste de liens dans un tableau et d'effectuer une addition, puis de remettre l'addition dans la liste de liens.

code :

#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 4

Nous pouvons les ajouter en utilisant la récursion. Supposons que la question soit définie comme suit : nous avons des listes l1 y l2 et nous voulons les additionner en stockant le résultat dans l1 . Pour simplifier, supposons que les deux listes ont la même longueur (le code peut être facilement modifié pour fonctionner avec des longueurs différentes). Voici ma solution Java fonctionnelle :

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 5

Input : List a , List b
Output : List c

La plupart des approches ici nécessitent un espace supplémentaire pour la liste a et la liste b. Cela peut être supprimé.

1. Inverser la liste a et la liste b pour qu'elles soient représentées dans l'ordre inverse (c'est-à-dire la queue comme la tête et tous les liens inversés) avec un espace constant de O(1).
2. Additionnez ensuite les listes de manière efficace en les parcourant toutes les deux simultanément et en maintenant un report.
3. Inversez la liste a et la liste b si nécessaire