Работа с односвязными списками. Реализовать функцию, объединяющую два списка и возвр. указатель на первый элемент нового списка

Question

Необходимо реализовать функцию, которая на вход принимает два указателя на node — начало соответствующих списков. Функция должна вернуть указатель на начало объединенного списка. Гарантируется, что данные списки не зациклены, а также что в последних ячейках списков указатели на следующий элемент нулевые. Ваш список должен содержать в себе все те же значения, что и данные два, и идти они должны по неубыванию. Пожалуйста, не надо зацикливать итоговый список. Вы можете делать с данными списками что угодно.

Вот мой код, однако он неоптимизирован (либо зацикливается, что маловероятно) и валит один из тестов (Time Limit Exceeded).

struct node {
    node *next;
    int val;
};

node *new_element(int d, node *head)
{
    node *nd = new node;
    nd->val = d;
    nd->next = nullptr;
    if (head == nullptr) {
        head = nd;
    } else {
        node *current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = nd;
    }
    return head;
}

node *merge(node *a, node *b) {
    node *c = nullptr;
    while (a != nullptr && b != nullptr) {
        if (a->val <= b->val) {
            c = new_element(a->val, c);
            a = a->next;
        } else {
            c = new_element(b->val, c);
            b = b->next;
        }
    }
    if (a == nullptr) {
        while (b != nullptr) {
            c = new_element(b->val, c);
            b = b->next;
        }
    } else {
        while (a != nullptr) {
            c = new_element(a->val, c);
            a = a->next;
        }
    }
    return c;
}

Ещё советовали использовать рекурсию, но я если честно не понимаю как и куда её здесь засунуть.

Answer 1

Вы реализовали слияние и сделали как новый список со сложностью O(n^2). Это очень медленно. Также работа с памятью занимает много лишнего времени. Быстрее будет если модифицировать node меняя указатели next при конструировании результата. Рекурсия - плохая идея. Стек не безграничный.

Вот как надо менять указатели, проверьте сами :

node *merge(node *a, node *b) {
    node * c ;
    if ( a != nullptr )
      if ( b != nullptr )
        if (a->val <= b->val) {
          c = a ;
          a = a -> next ; }
        else {
          c = b ;
          b = b -> next ; }
      else {
        c = a ;
        a = a -> next ; }
    else 
      if ( b != nullptr ) {
        c = b ;
        b = b -> next ; }
      else
        return nullptr ;
    // c - начало нового списка
    c -> next = nullptr ;
    node * i = c ;
    while (a != nullptr && b != nullptr) {
        if (a->val <= b->val) {
          i -> next = a ;
          i = a ;
          a = a->next;
        } else {
          i -> next = b ;
          i = b ;
          b = b->next; }
        i -> next = nullptr ;
    }
    // оставшийся кусочек списка просто прибавляем 
    // к результату
    if (a != nullptr)
      i -> next = a ;
    else
      i -> next = b ;
    return c;
}

БЛОГ НА HUSL

Работа с односвязными списками. Реализовать функцию, объединяющую два списка и возвр. указатель на первый элемент нового списка

Ответы (1 шт):