Рубрики

Найти пары с заданной суммой в двусвязном списке

Учитывая отсортированный двусвязный список положительных элементов, задача состоит в том, чтобы найти пары в двусвязном списке, сумма которых равна заданному значению x, без использования дополнительного пробела?
Пример:

Input : head : 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9
        x = 7
Output: (6, 1), (5,2)

Ожидаемая сложность по времени составляет O (n), а вспомогательное пространство — O (1).

Простой подход к этой задаче состоит в том, чтобы один за другим выбрать каждый узел и найти второй элемент, сумма которого равна x, в оставшемся списке путем перемещения в прямом направлении. Сложность времени для этой задачи будет O (n ^ 2), n общее количество узлов в двусвязном списке.

Эффективное решение этой проблемы такое же, как в этой статье. Вот алгоритм:

  • Инициализируйте две переменные-указатели, чтобы найти элементы-кандидаты в отсортированном двусвязном списке. Сначала инициализируйте с начала двусвязного списка, т.е. first = head и инициализировать second последним узлом двусвязного списка т.е. second = last_node .
  • Мы инициализируем первый и второй указатели как первый и последний узлы. Здесь у нас нет произвольного доступа, поэтому, чтобы найти второй указатель, мы просматриваем список, чтобы инициализировать второй.
  • Если текущая сумма первого и второго меньше, чем x, то мы двигаемся первыми в прямом направлении. Если текущая сумма первого и второго элемента больше, чем x, то мы двигаемся вторым в обратном направлении.
  • Условия завершения цикла также отличаются от массивов. Цикл завершается, когда любой из двух указателей становится NULL, или они пересекают друг друга (second-> next = first), или они становятся одинаковыми (first == second)

C ++

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

using namespace std;

  
// структура узла двусвязного списка

struct Node

{

    int data;

    struct Node *next, *prev;

};

  
// Функция для поиска пары, сумма которой равна заданному значению x.

void pairSum(struct Node *head, int x)

{

    // Установить два указателя, сначала на начало DLL

    // и второй до конца DLL.

    struct Node *first = head;

    struct Node *second = head;

    while (second->next != NULL)

         second = second->next;

  

    // Для отслеживания, если мы найдем пару или нет

    bool found = false;

  

    // Цикл завершается, когда один из двух указателей

    // становиться NULL или они пересекаются (second-> next

    // == первый), или они становятся одинаковыми (первый == второй)

    while (first != NULL && second != NULL &&

           first != second && second->next != first)

    {

         // пара найдена

         if ((first->data + second->data) == x)

         {

              found = true;

              cout << "(" << first->data<< ", "

                   << second->data << ")" << endl;

  

              // двигаться первым в направлении вперед

              first = first->next;

  

              // сдвинуть секунду назад

              second = second->prev;

          }

          else

          {

              if ((first->data + second->data) < x)

                 first = first->next;

              else

                 second = second->prev;

          }

      }

  

      // если пары нет

      if (found == false)

           cout << "No pair found";

}

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

void insert(struct Node **head, int data)

{

    struct Node *temp = new Node;

    temp->data = data;

    temp->next = temp->prev = NULL;

    if (!(*head))

        (*head) = temp;

    else

    {

        temp->next = *head;

        (*head)->prev = temp;

        (*head) = temp;

    }

}

  
// Драйвер программы

int main()

{

    struct Node *head = NULL;

    insert(&head, 9);

    insert(&head, 8);

    insert(&head, 6);

    insert(&head, 5);

    insert(&head, 4);

    insert(&head, 2);

    insert(&head, 1);

    int x = 7;

  

    pairSum(head, x);

  

    return 0;

}

Джава

// Java-программа для поиска
// пара с заданной суммой х.

class GFG

{

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

static class Node

{

    int data;

    Node next, prev;

};

  
// Функция для поиска пары, чья
// сумма равна заданному значению x.

static void pairSum( Node head, int x)

{

    // Сначала устанавливаем два указателя

    // к началу DLL

    // и второй до конца DLL.

    Node first = head;

    Node second = head;

    while (second.next != null)

        second = second.next;

  

    // Для отслеживания, если мы найдем пару или нет

    boolean found = false;

  

    // цикл завершается, когда либо

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

    // они пересекаются (second.next

    // == сначала), или они становятся одинаковыми

    // (первая == вторая)

    while (first != null && second != null &&

           first != second && second.next != first)

    {

        // пара найдена

        if ((first.data + second.data) == x)

        {

            found = true;

            System.out.println( "(" + first.data + 

                                ", "+ second.data + ")" );

  

            // двигаться первым в направлении вперед

            first = first.next;

  

            // сдвинуть секунду назад

            second = second.prev;

        }

        else

        {

            if ((first.data + second.data) < x)

                first = first.next;

            else

                second = second.prev;

        }

    }

  

    // если пары нет

    if (found == false)

        System.out.println("No pair found");

}

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

static Node insert(Node head, int data)

{

    Node temp = new Node();

    temp.data = data;

    temp.next = temp.prev = null;

    if (head == null)

        (head) = temp;

    else

    {

        temp.next = head;

        (head).prev = temp;

        (head) = temp;

    }

    return temp;

}

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

public static void main(String args[])

{

    Node head = null;

    head = insert(head, 9);

    head = insert(head, 8);

    head = insert(head, 6);

    head = insert(head, 5);

    head = insert(head, 4);

    head = insert(head, 2);

    head = insert(head, 1);

    int x = 7;

  

    pairSum(head, x);

}
}

  
// Этот код добавлен
// Арнаб Кунду

C #

// C # программа для поиска
// пара с заданной суммой х.

using System; 

  

class GFG 

  

    // структура узла

    // двусвязный список

    class Node 

    

        public int data; 

        public Node next, prev; 

    }; 

  

    // Функция для поиска пары, чья

    // сумма равна заданному значению x.

    static void pairSum( Node head, int x) 

    

        // Сначала устанавливаем два указателя

        // к началу DLL

        // и второй до конца DLL.

        Node first = head; 

        Node second = head; 

        while (second.next != null

            second = second.next; 

  

        // Для отслеживания, если мы найдем пару или нет

        bool found = false

  

        // цикл завершается, когда либо

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

        // они пересекаются (second.next

        // == сначала), или они становятся одинаковыми

        // (первая == вторая)

        while (first != null && second != null && 

            first != second && second.next != first) 

        

            // пара найдена

            if ((first.data + second.data) == x) 

            

                found = true

                Console.WriteLine( "(" + first.data + 

                                    ", "+ second.data + ")" ); 

  

                // двигаться первым в направлении вперед

                first = first.next; 

  

                // сдвинуть секунду назад

                second = second.prev; 

            

            else

            

                if ((first.data + second.data) < x) 

                    first = first.next; 

                else

                    second = second.prev; 

            

        

  

        // если пары нет

        if (found == false

            Console.WriteLine("No pair found"); 

    

  

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

    // новый узел в начале

    // двусвязного списка

    static Node insert(Node head, int data) 

    

        Node temp = new Node(); 

        temp.data = data; 

        temp.next = temp.prev = null

        if (head == null

            (head) = temp; 

        else

        

            temp.next = head; 

            (head).prev = temp; 

            (head) = temp; 

        

        return temp; 

    

  

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

    public static void Main(String []args) 

    

        Node head = null

        head = insert(head, 9); 

        head = insert(head, 8); 

        head = insert(head, 6); 

        head = insert(head, 5); 

        head = insert(head, 4); 

        head = insert(head, 2); 

        head = insert(head, 1); 

        int x = 7; 

  

        pairSum(head, x); 

    

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


Выход:

(1,6) 
(2,5)

Временная сложность: O (n)
Вспомогательное пространство: O (1)

Если связанный список не отсортирован, то мы можем отсортировать список в качестве первого шага. Но в этом случае общая сложность времени станет O (n Log n). Мы можем использовать хеширование в таких случаях, если дополнительное пространство не является ограничением. Решение на основе хеширования такое же, как метод 2 здесь .

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Найти пары с заданной суммой в двусвязном списке

0.00 (0%) 0 votes