Рубрики

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

Учитывая два числа, представленные двумя списками, напишите функцию, которая возвращает список сумм. Список сумм является представлением списка сложения двух входных чисел.

Пример :

Input: List1: 5->6->3  // represents number 365
       List2: 8->4->2 //  represents number 248
Output: Resultant list: 3->1->6  // represents number 613


Input: List1: 7->5->9->4->6  // represents number 64957
       List2: 8->4 //  represents number 48
Output: Resultant list: 5->0->0->5->6  // represents number 65005

Подход : переберите оба списка и выберите один за другим узлы обоих списков и добавьте значения. Если сумма больше 10, сделайте перенос как 1 и уменьшите сумму. Если в одном списке больше элементов, чем в другом, то оставшиеся значения этого списка следует считать равными 0.

Ниже приведена реализация этого подхода.

C ++

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

using namespace std;

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

class Node 

    public:

    int data; 

    Node* next; 

}; 

  
/ * Функция для создания нового узла с заданными данными * /

Node *newNode(int data) 

    Node *new_node = new Node();

    new_node->data = data; 

    new_node->next = NULL; 

    return new_node; 

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

void push(Node** head_ref, int new_data) 

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

    Node* new_node = newNode(new_data); 

  

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

    new_node->next = (*head_ref); 

  

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

    (*head_ref) = new_node; 

  
/ * Добавляет содержимое двух связанных списков и
вернуть головной узел результирующего списка * /
Node* addTwoLists (Node* first, Node* second) 

    Node* res = NULL; // res - головной узел результирующего списка

    Node *temp, *prev = NULL; 

    int carry = 0, sum; 

  

    while (first != NULL || second != NULL) // пока существуют оба списка

    

        // Рассчитать значение следующей цифры в результирующем списке.

        // Следующая цифра - сумма следующих вещей

        // (я несу

        // (ii) Следующая цифра первого списка (если есть следующая цифра)

        // (ii) Следующая цифра второго списка (если есть следующая цифра)

        sum = carry + (first? first->data: 0) +

                      (second? second->data: 0); 

  

        // обновляем перенос для следующего расчета

        carry = (sum >= 10)? 1 : 0; 

  

        // обновляем сумму, если она больше 10

        sum = sum % 10; 

  

        // Создать новый узел с суммой в качестве данных

        temp = newNode(sum); 

  

        // если это первый узел

        // установить его в качестве заголовка списка результатов

        if(res == NULL) 

            res = temp; 

              

        // Если это не первый

        // узел затем подключить его к остальным.

        else  

            prev->next = temp; 

  

        // Установить prev для следующей вставки

        prev = temp; 

  

        // Переместить первый и второй указатели на следующие узлы

        if (first) first = first->next; 

        if (second) second = second->next; 

    

  

    if (carry > 0) 

    temp->next = newNode(carry); 

  

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

    return res; 

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

void printList(Node *node) 

    while(node != NULL) 

    

        cout << node->data << " "

        node = node->next; 

    

    cout<<endl; 

  
/ * Код водителя * /

int main(void

    Node* res = NULL; 

    Node* first = NULL; 

    Node* second = NULL; 

  

    // создаем первый список 7-> 5-> 9-> 4-> 6

    push(&first, 6); 

    push(&first, 4); 

    push(&first, 9); 

    push(&first, 5); 

    push(&first, 7); 

    printf("First List is "); 

    printList(first); 

  

    // создаем второй список 8-> 4

    push(&second, 4); 

    push(&second, 8); 

    cout<<"Second List is "

    printList(second); 

  

    // Добавляем два списка и видим результат

    res = addTwoLists(first, second); 

    cout<<"Resultant list is "

    printList(res); 

  

return 0; 

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

С

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

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

struct Node

{

    int data;

    struct Node* next;

};

  
/ * Функция для создания нового узла с заданными данными * /

struct Node *newNode(int data)

{

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

    new_node->data = data;

    new_node->next = NULL;

    return new_node;

}

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

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

{

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

    struct Node* new_node = newNode(new_data);

  

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

    new_node->next = (*head_ref);

  

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

    (*head_ref)    = new_node;

}

  
/ * Добавляет содержимое двух связанных списков и возвращает головной узел результирующего списка * /

struct Node* addTwoLists (struct Node* first, struct Node* second)

{

    struct Node* res = NULL; // res - головной узел результирующего списка

    struct Node *temp, *prev = NULL;

    int carry = 0, sum;

  

    while (first != NULL || second != NULL) // пока существуют оба списка

    {

        // Рассчитать значение следующей цифры в результирующем списке.

        // Следующая цифра - сумма следующих вещей

        // (я несу

        // (ii) Следующая цифра первого списка (если есть следующая цифра)

        // (ii) Следующая цифра второго списка (если есть следующая цифра)

        sum = carry + (first? first->data: 0) + (second? second->data: 0);

  

        // обновляем перенос для следующего расчета

        carry = (sum >= 10)? 1 : 0;

  

        // обновляем сумму, если она больше 10

        sum = sum % 10;

  

        // Создать новый узел с суммой в качестве данных

        temp = newNode(sum);

  

        // если это первый узел, тогда установите его в качестве заголовка результирующего списка

        if(res == NULL)

            res = temp;

        else // Если это не первый узел, то подключите его к остальному.

            prev->next = temp;

  

        // Установить prev для следующей вставки

        prev  = temp;

  

        // Переместить первый и второй указатели на следующие узлы

        if (first) first = first->next;

        if (second) second = second->next;

    }

  

    if (carry > 0)

      temp->next = newNode(carry);

  

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

    return res;

}

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

void printList(struct Node *node)

{

    while(node != NULL)

    {

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

        node = node->next;

    }

    printf("\n");

}

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

int main(void)

{

    struct Node* res = NULL;

    struct Node* first = NULL;

    struct Node* second = NULL;

  

    // создаем первый список 7-> 5-> 9-> 4-> 6

    push(&first, 6);

    push(&first, 4);

    push(&first, 9);

    push(&first, 5);

    push(&first, 7);

    printf("First List is ");

    printList(first);

  

    // создаем второй список 8-> 4

    push(&second, 4);

    push(&second, 8);

    printf("Second List is ");

    printList(second);

  

    // Добавляем два списка и видим результат

    res = addTwoLists(first, second);

    printf("Resultant list is ");

    printList(res);

  

   return 0;

}

Джава

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

  

class LinkedList {

  

    static Node head1, head2;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d) {

            data = d;

            next = null;

        }

    }

  

    / * Добавляет содержимое двух связанных списков и возвращает головной узел результирующего списка * /

    Node addTwoLists(Node first, Node second) {

        Node res = null; // res - головной узел результирующего списка

        Node prev = null;

        Node temp = null;

        int carry = 0, sum;

  

        while (first != null || second != null) // пока существуют оба списка

        {

            // Рассчитать значение следующей цифры в результирующем списке.

            // Следующая цифра - сумма следующих вещей

            // (я несу

            // (ii) Следующая цифра первого списка (если есть следующая цифра)

            // (ii) Следующая цифра второго списка (если есть следующая цифра)

            sum = carry + (first != null ? first.data : 0)

                    + (second != null ? second.data : 0);

  

            // обновляем перенос для следующего расчета

            carry = (sum >= 10) ? 1 : 0;

  

            // обновляем сумму, если она больше 10

            sum = sum % 10;

  

            // Создать новый узел с суммой в качестве данных

            temp = new Node(sum);

  

            // если это первый узел, тогда установите его в качестве главы

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

            if (res == null) {

                res = temp;

            } else // Если это не первый узел, то подключите его к остальному.

            {

                prev.next = temp;

            }

  

            // Установить prev для следующей вставки

            prev = temp;

  

            // Переместить первый и второй указатели на следующие узлы

            if (first != null) {

                first = first.next;

            }

            if (second != null) {

                second = second.next;

            }

        }

  

        if (carry > 0) {

            temp.next = new Node(carry);

        }

  

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

        return res;

    }

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

  

    void printList(Node head) {

        while (head != null) {

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

            head = head.next;

        }

        System.out.println("");

    }

  

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

  

        // создаем первый список

        list.head1 = new Node(7);

        list.head1.next = new Node(5);

        list.head1.next.next = new Node(9);

        list.head1.next.next.next = new Node(4);

        list.head1.next.next.next.next = new Node(6);

        System.out.print("First List is ");

        list.printList(head1);

  

        // создание второго списка

        list.head2 = new Node(8);

        list.head2.next = new Node(4);

        System.out.print("Second List is ");

        list.printList(head2);

  

        // добавляем два списка и видим результат

        Node rs = list.addTwoLists(head1, head2);

        System.out.print("Resultant List is ");

        list.printList(rs);

    }

}

  
// этот код предоставлен Mayank Jaiswal

питон

# Программа Python для добавления двух чисел, представленных в связанном списке

  
# Класс узла

class Node:

  

    # Конструктор для инициализации объекта узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

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

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

    # Добавить содержимое двух связанных списков и вернуть заголовок

    # узел списка результатов

    def addTwoLists(self, first, second):

        prev = None

        temp = None

        carry = 0 

  

        # Пока существует оба списка

        while(first is not None or second is not None):

  

            # Рассчитать значение следующей цифры в

            # результирующий список

            # Следующая цифра - сумма следующих вещей

            # (я несу

            # (ii) Следующая цифра первого списка (если

            # следующая цифра)

            # (iii) Следующая цифра второго списка (если есть)

            # - следующая цифра)

            fdata = 0 if first is None else first.data

            sdata = 0 if second is None else second.data

            Sum = carry + fdata + sdata

  

            # обновить перенос для следующего расчета

            carry = 1 if Sum >= 10 else 0

  

            # обновить сумму, если она больше 10

            Sum = Sum if Sum < 10 else Sum % 10

  

            # Создать новый узел с суммой в качестве данных

            temp = Node(Sum)

  

            # если это первый узел, тогда установите его в качестве заголовка

            № результирующего списка

            if self.head is None:

                self.head = temp

            else :

                prev.next = temp 

  

            # Установить пред для следующей вставки

            prev = temp

  

            # Переместить первый и второй указатели на следующие узлы

            if first is not None:

                first = first.next

            if second is not None:

                second = second.next

  

        if carry > 0:

            temp.next = Node(carry)

  

    # Утилита для печати связанного LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print temp.data,

            temp = temp.next

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

first = LinkedList()

second = LinkedList()

  
# Создать первый список

first.push(6)

first.push(4)

first.push(9)

first.push(5)

first.push(7)

print "First List is ",

first.printList()

  
# Создать второй список

second.push(4)

second.push(8)

print "\nSecond List is ",

second.printList()

  
# Добавьте два списка и посмотрите результат

res = LinkedList()

res.addTwoLists(first.head, second.head)

print "\nResultant list is ",

res.printList()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

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

using System;

  

public class LinkedList

{

  

    Node head1, head2;

  

    public class Node 

    {

        public int data;

        public Node next;

  

        public Node(int d) 

        {

            data = d;

            next = null;

        }

    }

  

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

    и вернуть головной узел результирующего списка * /

    Node addTwoLists(Node first, Node second)

    {

        // res - головной узел результирующего списка

        Node res = null

        Node prev = null;

        Node temp = null;

        int carry = 0, sum;

  

        // пока существуют оба списка

        while (first != null || second != null

        {

            // Рассчитать значение следующей цифры в результирующем списке.

            // Следующая цифра - сумма следующих вещей

            // (я несу

            // (ii) Следующая цифра первого списка (если есть следующая цифра)

            // (ii) Следующая цифра второго списка (если есть следующая цифра)

            sum = carry + (first != null ? first.data : 0)

                    + (second != null ? second.data : 0);

  

            // обновляем перенос для следующего расчета

            carry = (sum >= 10) ? 1 : 0;

  

            // обновляем сумму, если она больше 10

            sum = sum % 10;

  

            // Создать новый узел с суммой в качестве данных

            temp = new Node(sum);

  

            // если это первый узел, тогда установите его в качестве главы

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

            if (res == null

            {

                res = temp;

            

              

            // Если это не первый

            // узел затем подключить его к остальным.

            else 

            {

                prev.next = temp;

            }

  

            // Установить prev для следующей вставки

            prev = temp;

  

            // Переместить первый и второй указатели на следующие узлы

            if (first != null)

            {

                first = first.next;

            }

            if (second != null

            {

                second = second.next;

            }

        }

  

        if (carry > 0)

        {

            temp.next = new Node(carry);

        }

  

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

        return res;

    }

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

  

    void printList(Node head) 

    {

        while (head != null

        {

            Console.Write(head.data + " ");

            head = head.next;

        }

    Console.WriteLine("");

    }

  

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

    public static void Main(String[] args) 

    {

        LinkedList list = new LinkedList();

  

        // создаем первый список

        list.head1 = new Node(7);

        list.head1.next = new Node(5);

        list.head1.next.next = new Node(9);

        list.head1.next.next.next = new Node(4);

        list.head1.next.next.next.next = new Node(6);

        Console.Write("First List is ");

        list.printList(list.head1);

  

        // создание второго списка

        list.head2 = new Node(8);

        list.head2.next = new Node(4);

        Console.Write("Second List is ");

        list.printList(list.head2);

  

        // добавляем два списка и видим результат

        Node rs = list.addTwoLists(list.head1, list.head2);

        Console.Write("Resultant List is ");

        list.printList(rs);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

  First List is 7 5 9 4 6
  Second List is 8 4
  Resultant list is 5 0 0 5 6

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

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

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

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

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

0.00 (0%) 0 votes