Предположим, что у вас есть 2 больших числа, представленных в виде связанных списков, как их добавить и сохранить результат в отдельном связанном списке. например,
a = 2 -> 1 -> 7
b = 3 -> 4
result = 2 -> 5 -> 1
Можете ли вы добавить их без изменения связанных списков
псевдокод:
Шаг 1. Перейдите по связанным спискам и нажмите элементы в двух разных стеках
Шаг 2. Поп верхние элементы из обоих стеков
Шаг 3. Добавьте элементы (+ любой перенос из предыдущих добавлений) и сохраните перенос в переменной temp
Шаг 4. Создайте node с суммой и вставьте ее в начало списка результатов
Я думаю, что это нечто вне контекста, но может быть очень полезным для человека, который изначально разместил этот вопрос.
Итак, вот рекомендация:
вместо того, чтобы использовать каждый node как одну цифру числа, используйте каждый node для хранения большого количества (близкого к размеру целого) и если максимально возможный номер, который вы выбрали для хранения в каждом node be x (ваш случай 9), то вы можете просмотреть свой номер как представление в base x+1.
где каждая цифра представляет собой число от 0 до x.
Это даст вам значительное увеличение производительности, так как алгоритм будет работать в O (log n) и потребует того же количества узлов, что и O (n) в вашем случае, n - число десятичных цифр большего размера два сложения.
Как правило, для удобства вашего алгоритма вы можете выбрать мощность 10 в качестве базы, которая соответствует диапазону вашего целого.
Например, если ваш номер равен 1234567890987654321, и вы хотите сохранить его в связанном списке, выбрав базу, чтобы быть 10 ^ 8, тогда ваше представление должно выглядеть так:
87654321- > 4567890 → 123 (маленький конец)
Вот моя хакерская попытка в Java, которая работает примерно в 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 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" в текущие node и '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 и добавьте это значение в соответствующий node списка целей.
без использования стека..... просто сохраните содержимое списка ссылок в массиве и выполните добавление, а затем снова добавьте добавление в список ссылок
код:
#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
В большинстве подходов здесь требуется дополнительное пространство для списка 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 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;
}
Конечная версия (нет разворота списка, без рекурсии):
#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;
}
В 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;
}
}
Вот моя первая попытка:
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
/* spoiler: будет просто рекурсия */
#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;
}