Рубрики

Пересечение двух отсортированных связанных списков

Если два списка отсортированы в порядке возрастания, создайте и верните новый список, представляющий пересечение двух списков. Новый список должен быть создан с собственной памятью — оригинальные списки не должны быть изменены.

Например, пусть первый связанный список будет 1-> 2-> 3-> 4-> 6, а второй связанный список будет 2-> 4-> 6-> 8, тогда ваша функция должна создать и вернуть третий список как 2 -> 4-> 6.

Метод 1 (с использованием фиктивного узла)
Стратегия здесь использует временный фиктивный узел в качестве начала списка результатов. Хвост указателя всегда указывает на последний узел в списке результатов, поэтому добавлять новые узлы легко. Пустой узел дает хвосту что-то, на что он должен указывать изначально, когда список результатов пуст. Этот фиктивный узел является эффективным, поскольку он является только временным и размещается в стеке. Цикл продолжается, удаляя один узел из «a» или «b» и добавляя его в tail. Когда мы закончим, результат будет в dummy.next.

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

   
/ * Узел списка ссылок * /

struct Node

{

    int data;

    struct Node* next;

};

  

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

  
/ * Это решение использует временную пустышку для построения списка результатов * /

struct Node* sortedIntersect(struct Node* a, struct Node* b)

{

  struct Node dummy;

  struct Node* tail = &dummy;

  dummy.next = NULL;

   

  / * Как только один или другой список заканчивается - мы закончили * /

  while (a != NULL && b != NULL)

  {

    if (a->data == b->data)

    {

       push((&tail->next), a->data);

       tail = tail->next;

       a = a->next;

       b = b->next;

    }

    else if (a->data < b->data) / * продвигать меньший список * /      

       a = a->next;

    else

       b = b->next;

  }

  return(dummy.next);

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла при порождении связанного списка * /

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;

  }

}

   
/ * Сушилка для тестирования вышеуказанных функций * /

int main()

{

  / * Начнем с пустых списков * /

  struct Node* a = NULL;

  struct Node* b = NULL;

  struct Node *intersect = NULL;

   

  / * Давайте создадим первый отсортированный связанный список для проверки функций

   Созданный связанный список будет 1-> 2-> 3-> 4-> 5-> 6 * /

  push(&a, 6);

  push(&a, 5);

  push(&a, 4);

  push(&a, 3);

  push(&a, 2);

  push(&a, 1);                                   

   

  / * Давайте создадим второй отсортированный связанный список

   Созданный связанный список будет 2-> 4-> 6-> 8 * /

  push(&b, 8);

  push(&b, 6);

  push(&b, 4);

  push(&b, 2);                                    

   

  / * Найти пересечение двух связанных списков * /

  intersect = sortedIntersect(a, b);

   

  printf("\n Linked list containing common items of a & b \n ");

  printList(intersect);           

   

  getchar();

}

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

Способ 2 (с использованием локальных ссылок)
Это решение структурно очень похоже на вышеприведенное, но оно избегает использования фиктивного узла. Вместо этого оно поддерживает указатель структурного узла **, lastPtrRef, который всегда указывает на последний указатель в списке результатов. Это решает тот же случай, что и фиктивный узел — работа со списком результатов, когда он пуст. Если вы пытаетесь создать список в его хвосте, можно использовать фиктивный узел или структуру узла ** «ссылка»

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

   
/ * Узел списка ссылок * /

struct Node

{

    int data;

    struct Node* next;

};

  

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

  
/ * В этом решении используется локальная ссылка * /

struct Node* sortedIntersect(struct Node* a, struct Node* b)

{

  struct Node* result = NULL;

  struct Node** lastPtrRef = &result;

   

  / * Предварительное сравнение первых узлов в обоих списках.

    Когда тот или иной список заканчивается, мы закончили. * /

  while (a!=NULL && b!=NULL)

  {

    if (a->data == b->data)

    {

      / * нашел узел для пересечения * /

      push(lastPtrRef, a->data);

      lastPtrRef = &((*lastPtrRef)->next);

      a = a->next;

      b = b->next;

    }

    else if (a->data < b->data)

      a=a->next;       / * продвигать меньший список * /    

    else    

      b=b->next;    

  }

  return(result);

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла при порождении связанного списка * /

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;

  }

}

   
/ * Сушилка для тестирования вышеуказанных функций * /

int main()

{

  / * Начнем с пустых списков * /

  struct Node* a = NULL;

  struct Node* b = NULL;

  struct Node *intersect = NULL;

   

  / * Давайте создадим первый отсортированный связанный список для проверки функций

   Созданный связанный список будет 1-> 2-> 3-> 4-> 5-> 6 * /

  push(&a, 6);

  push(&a, 5);

  push(&a, 4);

  push(&a, 3);

  push(&a, 2);

  push(&a, 1);                                   

   

  / * Давайте создадим второй отсортированный связанный список

   Созданный связанный список будет 2-> 4-> 6-> 8 * /

  push(&b, 8);

  push(&b, 6);

  push(&b, 4);

  push(&b, 2);                                    

   

  / * Найти пересечение двух связанных списков * /

  intersect = sortedIntersect(a, b);

   

  printf("\n Linked list containing common items of a & b \n ");

  printList(intersect);           

   

  getchar();

}

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

Метод 3 (рекурсивный)
Ниже приведена рекурсивная реализация sortedIntersect ().

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

  
/ * Узел списка ссылок * /

struct Node

{

    int data;

    struct Node* next;

};

  

struct Node *sortedIntersect(struct Node *a, struct Node *b)

{

    /* базовый вариант */

    if (a == NULL || b == NULL)

        return NULL;

  

    / * Если оба списка не пусты * /

  

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

    if (a->data < b->data)

        return sortedIntersect(a->next, b);

  

    if (a->data > b->data)

        return sortedIntersect(a, b->next);

  

    // Ниже строки выполняются только когда a-> data == b-> data

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

    temp->data = a->data;

  

    / * продвигать оба списка и рекурсивно вызывать * /

    temp->next = sortedIntersect(a->next, b->next);

    return temp;

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла при порождении связанного списка * /

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;

    }

}

  
/ * Сушилка для тестирования вышеуказанных функций * /

int main()

{

    / * Начнем с пустых списков * /

    struct Node* a = NULL;

    struct Node* b = NULL;

    struct Node *intersect = NULL;

  

    / * Давайте создадим первый отсортированный связанный список для проверки функций

     Созданный связанный список будет 1-> 2-> 3-> 4-> 5-> 6 * /

    push(&a, 6);

    push(&a, 5);

    push(&a, 4);

    push(&a, 3);

    push(&a, 2);

    push(&a, 1);

  

    / * Давайте создадим второй отсортированный связанный список

     Созданный связанный список будет 2-> 4-> 6-> 8 * /

    push(&b, 8);

    push(&b, 6);

    push(&b, 4);

    push(&b, 2);

  

    / * Найти пересечение двух связанных списков * /

    intersect = sortedIntersect(a, b);

  

    printf("\n Linked list containing common items of a & b \n ");

    printList(intersect);

  

    return 0;

}

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

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

Ссылки:
cslibrary.stanford.edu/105/LinkedListProblems.pdf

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

Пересечение двух отсортированных связанных списков

0.00 (0%) 0 votes