c программа для добавления двух односвязных списков неравной длины, содержащих однозначные числа во всех их узлах

Question

я получил это как вопрос для интервью. мне дали 2 связанных списка неравной длины, содержащих одно цифру в каждом из их узлов. меня попросили построить третий связанный список, который содержит сумму двух связанных списков, снова в форме 1 цифры в узле. например: связанный список 1 4-7-9-6 связанный список 2 5-7 тогда третий связанный список будет 4-8-5-3 Может ли кто-нибудь предложить мне эффективный алгоритм с минимальным компромиссом в плане сложности пространства?

Answer 1

1. Обратные списки 1 и 2
2. Суммируйте поэлементно (сохраняя перенос), помещая результаты в список 3, который вы строите от хвоста к голове

ИЛИ

1. Преобразование списков 1 и 2 в целые числа (например, int list1AsInt = 0; For each node {list1AsInt *= 10; list1AsInt += valueOfThisNode;})
2. Суммирование этих чисел
3. Преобразование результата в связанный список (например,valueOfBrandNewNode = list3AsInt % 10; list3AsInt /= 10; Add a new node that points to the prev one;)

ИЛИ

1. Пройдите по обоим спискам один раз, чтобы узнать их длину.Для этого примера предположим, что список 1 длиннее на N узлов.
2. Создайте список 3 для представления суммы без переносов и список 4 для представления переносов.
3. Для первого Nузлы списка 1, скопируйте эти значения в список 3 и сделайте значения списка 4 равными 0.
4. Для остальных узлов списков 1 и 2 сумма поэлементно суммируется, а сумма сумм 10 в списке 3и перенос по списку 4. Отслеживайте с помощью bool, является ли список 4 всеми 0.
5. Добавьте последний узел со значением 0 в список 4.
6. Если список 4 полностью равен 0,сделанный.Иначе, перейдите к шагу 2, рассматривая список 3 как новый список 1 и список 4 как новый список 2. Мы знаем, что длина нового списка 1 больше длины старых списков 1 и 2 и длиныиз нового списка 2 еще на один.

Answer 2

Это просто.Предполагая, что самый левый узел является наиболее значимым битом.Выровняйте два списка, добавьте и распространяйте перенос.По возвращении создайте новый узел, если требуется.

#include <stdio.h>


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


    int listadd (struct list  *l1, struct list *l2) {

        if ((l1 == NULL) || (l2 == NULL))
                return;
        int carry = 0;

        if ((l1->next == NULL) && (l2->next != NULL)) {
                carry += listadd (l1, l2->next) + l2->val;
                return carry;
        }

        else if ((l1->next != NULL) && (l2->next == NULL)) {
                carry +=listadd (l1->next, l2);
                l1->val = l1->val + carry;
        }
        else if ((l1->next != NULL) && (l2->next != NULL)) {
                carry += listadd (l1->next, l2->next);
        }
        else if ((l1->next == NULL) && (l2->next == NULL)) {
                l1->val = l1->val + l2->val;
                carry = l1->val/10;
                l1->val = l1->val%10;
                return carry;
        }

        carry = l1->val/10;
        l1->val = l1->val%10;
        return carry;
}

struct list * createnode (int val) {
  struct list * temp = (struct list *) malloc (sizeof(struct list));
  temp->val = val;
  temp->next = NULL;
  return temp;
}

int main() {
   int carry = 0;
   struct list *l1 = createnode(1);
l1->next = createnode(2);

   struct list *l2 = createnode(7);
   l2->next = createnode(8);

  carry = listadd(l1,l2);

  if (carry != 0) {
        struct list * temp = createnode(carry);
        temp->next = l1;
        l1 = temp;
  }


   while (l1!= NULL) {
        printf ("%d", l1->val);
        l1=l1->next;
   }
}

Answer 3

Посмотрите на этот код:

node *add_two_linkedlist(node *head1,node *head2)
{
    int i,j,temp;
    node *p,*n;
    p=head1;
    n=head2;
    i=count(head1);
    j=count(head2);

    if(i>j)
    {
        while(j!=0)
        {
            p->data=p->data+n->data;
            if(p->data>10)
            {
                temp=(p->data)/10;
                p->data=(p->data)%10;
                p=p->next;
                n=n->next;
                p=p->data+temp;
                j--;
            }               
        }   
        return head1;
    }

    if(j>i)
    {
        while(i!=0)
        {
            n->data=p->data+n->data;
            if(n->data>10)
            {
                temp=(n->data)/10;
                n->data=(n->data)%10;
                n=n->next;
                p=p->next;
                n=n->data+temp;
                i--;
            }               
        }   
        return head2;
    }
}

Answer 4

Решение может быть намного проще, если список хранит числа в обратном порядке.

Тем не менее, с учетом данного ограничения, здесь есть подход.

1. найти nthToLast цифру обоих списков, начиная с n = 0,
2. создать node с суммой цифр,
3. обновить (работает) carry,
4. insert вновь созданный узел в списке head of result

Ниже приведен (непроверенный) код С.

typedef struct DigitNode_ {
    int digit;
    struct DigitNode_ * next;
} DigitNode;

/*  Returns the n-th element from the end of the SLL;
    if no such element exists, then return NULL.
    See: /2280751/kak-naiti-n-i-element-v-kontse-odnosvyaznogo-spiska
*/
extern DigitNode * nthNodeFromTail( DigitNode * listHead, size_t n );

/*  Push pNode in the front, i.e. as the new head of the list */
extern void pushFront( DigitNode ** pListHead, DigitNode * pNode );

/*  Create new list as sum of a and b, and return the head of the new list.
        a -> 4 -> 7 -> 9 -> 6 -> NULL
        b ->           5 -> 7 -> NULL
    results in
        c -> 4 -> 8 -> 5 -> 3 -> NULL
*/
DigitNode * sumDigitLists( DigitNode * a, DigitNode * b ) {

    DigitNode * c = 0;
    int carry = 0;

    /* i is the position of a node from the tail of the list, backwards */
    for( size_t i = 0; /* see 'break' inside */; i++ ) {

        const DigitNode * const ithNodeA = nthNodeFromTail( a, i );
        const DigitNode * const ithNodeB = nthNodeFromTail( b, i );

        /* Stop when processing of both lists are finished */
        if( !ithNodeA && !ithNodeB ) {
            break;
        }

        const int ithDigitA = ithNodeA ? ithNodeA->digit : 0;
        const int ithDigitB = ithNodeB ? ithNodeB->digit : 0;

        assert( (0 <= ithDigitA) && (ithDigitA <= 9) );
        assert( (0 <= ithDigitB) && (ithDigitB <= 9) );

        const int conceptualIthDigitC = carry + ithDigitA + ithDigitB;
        const int ithDigitC = conceptualIthDigitC % 10;
        carry = conceptualIthDigitC / 10;

        DigitNode ithNodeC = { ithDigitC, NULL };
        pushFront( &c, &ithNodeC ); 
    }

    return c;
}

Answer 5

Если списки связаны дважды, это просто:

1. Обойти оба списка до конца.
2. Добавить цифры в соответствующих узлах и сохранить цифру переноса.
3. Создать узел в списке 3.
4. Переместить один узел к началу списков и повторить.

Answer 6

1. Считать каждую цифру как ее эквивалент ASCII в массив символов, индексированный от 0, для обоих списков.
2. Используйте функцию atoi() для обоих массивов символов (вы можете использовать atol() или atoll(), если вас беспокоит длина)
3. Добавить оба числа
4. Используйте функцию itoa(), чтобы преобразовать в массив символов и затем вернуть в новый список.

Хотя, я допускаю, что функция itoa() не является стандартной.