Рубрики

Добавьте два числа, представленные связанными списками | Набор 2

Учитывая два числа, представленные двумя связанными списками, напишите функцию, которая возвращает список сумм. Список сумм представляет собой связанный список представлений сложения двух входных чисел. Не разрешается изменять списки. Также не допускается использование явного дополнительного пространства (подсказка: используйте рекурсию).

пример

Input:
  First List: 5->6->3  // represents number 563
  Second List: 8->4->2 //  represents number 842
Output
  Resultant list: 1->4->0->5  // represents number 1405

Мы обсудили решение здесь , которое для связанных списков , где наименее значимая цифра является первым узлом списков и наиболее значимой цифрой является последним узлом. В этой задаче наиболее значимый узел — это первый узел, а наименее значимая цифра — последний узел, и нам не разрешено изменять списки. Рекурсия используется здесь для вычисления суммы справа налево.

Ниже приведены шаги.
1) Рассчитать размеры данных двух связанных списков.
2) Если размеры одинаковы, то рассчитайте сумму с помощью рекурсии. Удерживайте все узлы в стеке рекурсивных вызовов до крайнего правого узла, вычислите сумму крайних правых узлов и перенесите прямой перенос в левую сторону.
3) Если размер не совпадает, выполните следующие шаги:
…. а) Рассчитать разницу размеров двух связанных списков. Пусть разница будет дифф
…. б) Переместить узлы diff вперед в большом связанном списке. Теперь используйте шаг 2, чтобы вычислить сумму меньшего списка и правого подсписка (того же размера) большего списка. Кроме того, храните перенос этой суммы.
…. c) Рассчитайте сумму переноса (рассчитанную на предыдущем шаге) с оставшимся левым подсписком большего списка. Узлы этой суммы добавляются в начало списка сумм, полученного на предыдущем шаге.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже на рисунке приведена реализация вышеуказанного подхода.

C ++

// C ++ рекурсивная программа для добавления двух связанных списков
#include <bits/stdc++.h>

using namespace std;

  
// связанный узел списка

class Node 

    public:

    int data; 

    Node* next; 

}; 

  

typedef Node node; 

  
/ * Полезная функция для вставки
узел в начале связанного списка * /

void push(Node** head_ref, int new_data) 

    / * выделить узел * /

    Node* new_node = new Node[(sizeof(Node))]; 

  

    / * вставить данные * /

    new_node->data = new_data; 

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref); 

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node; 

  
/ * Утилита для печати связанного списка * /

void printList(Node *node) 

    while (node != NULL) 

    

        cout<<node->data<<" "

        node = node->next; 

    

    cout<<endl; 

  
// Утилита для замены двух указателей

void swapPointer( Node** a, Node** b ) 

    node* t = *a; 

    *a = *b; 

    *b = t; 

  
/ * Утилита для получения размера связанного списка * /

int getSize(Node *node) 

    int size = 0; 

    while (node != NULL) 

    

        node = node->next; 

        size++; 

    

    return size; 

  
// Добавляет два связанных списка одинакового размера
// представлен head1 и head2 и возвращает
// заголовок результирующего связанного списка. Нести
// распространяется при возврате из рекурсии

node* addSameSize(Node* head1, Node* head2, int* carry) 

    // Поскольку функция предполагает, что связанные списки имеют одинаковый размер,

    // проверяем любой из двух указателей головы

    if (head1 == NULL) 

        return NULL; 

  

    int sum; 

  

    // Выделим память для суммы узлов текущих двух узлов

    Node* result = new Node[(sizeof(Node))]; 

  

    // Рекурсивно добавляем оставшиеся узлы и получаем перенос

    result->next = addSameSize(head1->next, head2->next, carry); 

  

    // добавляем цифры текущих узлов и распространяемого переноса

    sum = head1->data + head2->data + *carry; 

    *carry = sum / 10; 

    sum = sum % 10; 

  

    // Назначаем сумму текущему узлу результирующего списка

    result->data = sum; 

  

    return result; 

  
// Эта функция вызывается после
// меньший список добавляется к большему
// список подсписков того же размера. Однажды
// добавлен правый подсписок, перенос
// должен быть добавлен к левой стороне большего
// список, чтобы получить окончательный результат.

void addCarryToRemaining(Node* head1, Node* cur, 

                        int* carry, Node** result) 

    int sum; 

  

    // Если дифф. количество узлов не пройдено, добавить перенос

    if (head1 != cur) 

    

        addCarryToRemaining(head1->next, cur, carry, result); 

  

        sum = head1->data + *carry; 

        *carry = sum/10; 

        sum %= 10; 

  

        // добавить этот узел в начало результата

        push(result, sum); 

    

  
// Основная функция, которая добавляет два связанных списка
// представлен head1 и head2. Сумма
// два списка хранятся в списке, указанном по результату

void addList(Node* head1, Node* head2, Node** result) 

    Node *cur; 

  

    // первый список пуст

    if (head1 == NULL) 

    

        *result = head2; 

        return

    

  

    // второй список пуст

    else if (head2 == NULL) 

    

        *result = head1; 

        return

    

  

    int size1 = getSize(head1); 

    int size2 = getSize(head2) ; 

  

    int carry = 0; 

  

    // Добавить списки одинакового размера

    if (size1 == size2) 

        *result = addSameSize(head1, head2, &carry); 

  

    else

    

        int diff = abs(size1 - size2); 

  

        // Первый список всегда должен быть больше второго.

        // Если нет, поменяйте местами указатели

        if (size1 < size2) 

            swapPointer(&head1, &head2); 

  

        // переместить дифференциал количество узлов в первом списке

        for (cur = head1; diff--; cur = cur->next); 

  

        // получаем добавление списков одинакового размера

        *result = addSameSize(cur, head2, &carry); 

  

        // получить добавление оставшегося первого списка и продолжить

        addCarryToRemaining(head1, cur, &carry, result); 

    

  

    // если какой-то перенос еще есть, добавьте новый узел к фронту

    // список результатов. например, 999 и 87

    if (carry) 

        push(result, carry); 

  
// Код драйвера

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]); 

  

    // Создать первый список как 9-> 9-> 9

    int i; 

    for (i = size1-1; i >= 0; --i) 

        push(&head1, arr1[i]); 

  

    // Создать второй список как 1-> 8

    for (i = size2-1; i >= 0; --i) 

        push(&head2, arr2[i]); 

  

    addList(head1, head2, &result); 

  

    printList(result); 

  

    return 0; 

  

  
// Этот код предоставлен rathbhupendra

С

// Рекурсивная программа для добавления двух связанных списков

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

  
// связанный узел списка

struct Node

{

    int data;

    struct Node* next;

};

  

typedef struct Node node;

  
/ * Полезная функция для вставки узла в начало связанного списка * /

void push(struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

  

    / * вставить данные * /

    new_node->data  = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref)    = new_node;

}

  
/ * Утилита для печати связанного списка * /

void printList(struct Node *node)

{

    while (node != NULL)

    {

        printf("%d  ", node->data);

        node = node->next;

    }

    printf("n");

}

  
// Утилита для замены двух указателей

void swapPointer( Node** a, Node** b )

{

    node* t = *a;

    *a = *b;

    *b = t;

}

  
/ * Утилита для получения размера связанного списка * /

int getSize(struct Node *node)

{

    int size = 0;

    while (node != NULL)

    {

        node = node->next;

        size++;

    }

    return size;

}

  
// Добавляет два связанных списка одинакового размера, представленных head1 и head2, и возвращает
// заголовок результирующего связанного списка. Нести распространяется при возвращении из
// рекурсия

node* addSameSize(Node* head1, Node* head2, int* carry)

{

    // Поскольку функция предполагает, что связанные списки имеют одинаковый размер,

    // проверяем любой из двух указателей головы

    if (head1 == NULL)

        return NULL;

  

    int sum;

  

    // Выделим память для суммы узлов текущих двух узлов

    Node* result = (Node *)malloc(sizeof(Node));

  

    // Рекурсивно добавляем оставшиеся узлы и получаем перенос

    result->next = addSameSize(head1->next, head2->next, carry);

  

    // добавляем цифры текущих узлов и распространяемого переноса

    sum = head1->data + head2->data + *carry;

    *carry = sum / 10;

    sum = sum % 10;

  

    // Назначаем сумму текущему узлу результирующего списка

    result->data = sum;

  

    return result;

}

  
// Эта функция вызывается после добавления меньшего списка к большему
// список подсписков того же размера. Как только правильный список добавлен, перенос
// необходимо добавить слева от большего списка, чтобы получить окончательный результат.

void addCarryToRemaining(Node* head1, Node* cur, int* carry, Node** result)

{

    int sum;

  

    // Если дифф. количество узлов не пройдено, добавить перенос

    if (head1 != cur)

    {

        addCarryToRemaining(head1->next, cur, carry, result);

  

        sum = head1->data + *carry;

        *carry = sum/10;

        sum %= 10;

  

        // добавить этот узел в начало результата

        push(result, sum);

    }

}

  
// Основная функция, которая добавляет два связанных списка, представленных head1 и head2.
// Сумма двух списков сохраняется в списке, указанном по результату

void addList(Node* head1, Node* head2, Node** result)

{

    Node *cur;

  

    // первый список пуст

    if (head1 == NULL)

    {

        *result = head2;

        return;

    }

  

    // второй список пуст

    else if (head2 == NULL)

    {

        *result = head1;

        return;

    }

  

    int size1 = getSize(head1);

    int size2 = getSize(head2) ;

  

    int carry = 0;

  

    // Добавить списки одинакового размера

    if (size1 == size2)

        *result = addSameSize(head1, head2, &carry);

  

    else

    {

        int diff = abs(size1 - size2);

  

        // Первый список всегда должен быть больше второго.

        // Если нет, поменяйте местами указатели

        if (size1 < size2)

            swapPointer(&head1, &head2);

  

        // переместить дифференциал количество узлов в первом списке

        for (cur = head1; diff--; cur = cur->next);

  

        // получаем добавление списков одинакового размера

        *result = addSameSize(cur, head2, &carry);

  

        // получить добавление оставшегося первого списка и продолжить

        addCarryToRemaining(head1, cur, &carry, result);

    }

  

    // если какой-то перенос еще есть, добавьте новый узел к фронту

    // список результатов. например, 999 и 87

    if (carry)

        push(result, carry);

}

  
// Программа драйвера для проверки вышеуказанных функций

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]);

  

    // Создать первый список как 9-> 9-> 9

    int i;

    for (i = size1-1; i >= 0; --i)

        push(&head1, arr1[i]);

  

    // Создать второй список как 1-> 8

    for (i = size2-1; i >= 0; --i)

        push(&head2, arr2[i]);

  

    addList(head1, head2, &result);

  

    printList(result);

  

    return 0;

}

Джава

// Java-программа для добавления двух связанных списков

  

public class linkedlistATN 

{

    class node 

    {

        int val;

        node next;

  

        public node(int val) 

        {

            this.val = val;

        }

    }

      

    // Функция для печати связанного списка

    void printlist(node head) 

    {

        while (head != null

        {

            System.out.print(head.val + " ");

            head = head.next;

        }

    }

  

    node head1, head2, result;

    int carry;

  

    / * Утилита для отправки значения в связанный список * /

    void push(int val, int list) 

    {

        node newnode = new node(val);

        if (list == 1

        {

            newnode.next = head1;

            head1 = newnode;

        

        else if (list == 2

        {

            newnode.next = head2;

            head2 = newnode;

        

        else 

        {

            newnode.next = result;

            result = newnode;

        }

  

    }

  

    // Добавляет два связанных списка одинакового размера, представленных

    // head1 и head2 и возвращает голову результирующего

    // связанный список. Нести распространяется при возвращении

    // из рекурсии

    void addsamesize(node n, node m) 

    {

        // Поскольку функция предполагает, что связанные списки имеют

        // одного размера, проверьте любой из двух указателей головы

        if (n == null)

            return;

  

        // Рекурсивно добавляем оставшиеся узлы и получаем перенос

        addsamesize(n.next, m.next);

  

        // добавляем цифры текущих узлов и распространяемого переноса

        int sum = n.val + m.val + carry;

        carry = sum / 10;

        sum = sum % 10;

  

        // Переместить это в список результатов

        push(sum, 3);

  

    }

  

    node cur;

  

    // Эта функция вызывается после того, как меньший список

    // добавлен в подсписок больших списков того же размера.

    // После добавления нужного подсписка перенос должен быть

    // добавлено в левую часть большего списка, чтобы получить

    // конечный результат.

    void propogatecarry(node head1) 

    {

        // Если дифф. количество узлов не пройдено, добавить перенос

        if (head1 != cur) 

        {

            propogatecarry(head1.next);

            int sum = carry + head1.val;

            carry = sum / 10;

            sum %= 10;

  

            // добавить этот узел в начало результата

            push(sum, 3);

        }

    }

  

    int getsize(node head) 

    {

        int count = 0;

        while (head != null

        {

            count++;

            head = head.next;

        }

        return count;

    }

  

    // Основная функция, которая добавляет два связанных списка

    // представлен head1 и head2. Сумма двух

    // списки хранятся в списке, указанном по результату

    void addlists() 

    {

        // первый список пуст

        if (head1 == null

        {

            result = head2;

            return;

        }

  

        // первый список пуст

        if (head2 == null

        {

            result = head1;

            return;

        }

  

        int size1 = getsize(head1);

        int size2 = getsize(head2);

  

        // Добавить списки одинакового размера

        if (size1 == size2) 

        {

            addsamesize(head1, head2);

        

        else 

        {

            // Первый список всегда должен быть больше второго.

            // Если нет, поменяйте местами указатели

            if (size1 < size2) 

            {

                node temp = head1;

                head1 = head2;

                head2 = temp;

            }

            int diff = Math.abs(size1 - size2);

  

            // переместить дифференциал количество узлов в первом списке

            node temp = head1;

            while (diff-- >= 0

            {

                cur = temp;

                temp = temp.next;

            }

  

            // получаем добавление списков одинакового размера

            addsamesize(cur, head2);

  

            // получить добавление оставшегося первого списка и продолжить

            propogatecarry(head1);

        }

            // если какой-то перенос еще есть, добавьте новый узел в

            // перед списком результатов. например, 999 и 87

            if (carry > 0)

                push(carry, 3);

          

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        linkedlistATN list = new linkedlistATN();

        list.head1 = null;

        list.head2 = null;

        list.result = null;

        list.carry = 0;

        int arr1[] = { 9, 9, 9 };

        int arr2[] = { 1, 8 };

  

        // Создать первый список как 9-> 9-> 9

        for (int i = arr1.length - 1; i >= 0; --i)

            list.push(arr1[i], 1);

  

        // Создать второй список как 1-> 8

        for (int i = arr2.length - 1; i >= 0; --i)

            list.push(arr2[i], 2);

  

        list.addlists();

  

        list.printlist(list.result);

    }

}

  
// Этот код предоставлен Rishabh Mahrsee


Выход:

1  0  1  7

Сложность времени: O (m + n), где m и n — размеры заданных двух связанных списков.

Связанная статья: Добавьте два числа, представленные связанными списками | Комплект 1

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Добавьте два числа, представленные связанными списками | Набор 2

0.00 (0%) 0 votes