Поменять местами связанный список в c - PullRequest
Новая
       18

Поменять местами связанный список в c

0 голосов
/ 03 марта 2019

Учитывая список, я хочу изменить список, поменяв местами первое с последним, второе со вторым последним и т. Д.

Я написал эту функцию, чтобы поменять местами каждую пару, где pos1 и pos2 - это две позиции, которые нужно поменять местами.

maxPos - это наибольшая из двух позиций, node1 и node2 - это две вершины, найденные после обхода списка. 

int swap(struct node *list, int pos1, int pos2) {

    if (node1 != NULL && node2 != NULL) {
        if (prev1 != NULL)
            prev1->next = node2;
        if (prev2 != NULL)
            prev2->next = node1;
        temp        = node1->next;
        node1->next = node2->next;
        node2->next = temp;
        if (prev1 == NULL)
            head = node2;
        else if (prev2 == NULL)
            head = node1;
    }
    return 1;
}

Вместо того, чтобы вызывать это рекурсивно для каждой пары, т.е.(1,n-1), (2,n-2), (3,n-3), для которого он должен каждый раз проходить по списку, мне было интересно, есть ли способ решить его итеративно.

Ответы [ 3 ]

0 голосов
/ 03 марта 2019

Вы действительно хотите поменять местами содержимое узла?

Вы можете итерационно перевернуть список с помощью очень простой функции: 

struct node {
    // whatever payload fields...
    struct node *next;
};

struct node *reverse_list(struct node *list) {
    struct node *last = NULL;
    while (list != NULL) {
        struct node *next = list->next;
        list->next = last;
        last = list;
        list = next;
    }
    return last;
}
0 голосов
/ 04 марта 2019

При использовании списка с элементом привязки (например, первый элемент является узлом, но не используется для хранения данных), вы можете использовать 

struct node **list_nth(struct node *node, size_t idx)
{
    for (;idx > 0 && node; --idx)
        node = node->next;

    return node ? &(node->next) : NULL;
}

void list_swap(struct node *head, size_t idx_a, size_t idx_b)
{
    struct node **a = list_nth(head, min(idx_a, idx_b));
    struct node **b = list_nth(head, max(idx_a, idx_b));
    struct node *tmp;

    if (idx_a == idx_b)
        return;

    if (!a || !b)
        abort();

    if ((*a)->next == *b) {
        tmp = *a;

        *a  = *b;
        tmp->next = (*b)->next;
        (*a)->next = tmp;
    } else {
        tmp        = (*a)->next;
        (*a)->next = (*b)->next;
        (*b)->next = tmp;

        tmp = *a;
        *a  = *b;
        *b  = tmp;
    }
}

для операции подкачки.Но для одиночных связанных списков обратная операция имеет сложность O (n ^ 2) из-за дорогостоящего поиска узлов.

Как уже было отмечено, для обращения к списку:

  • используйте двойную связь
  • итерируйте ее в обратном порядке с O (n)
  • удалите элемент (O (1))
  • добавьте элемент к новой голове(O (1))
  • объединить новый список со старым обратно (O (1))
0 голосов
/ 03 марта 2019

Вам нужно будет объявить новый метод обращения всего списка, который будет вызываться только один раз.Также вам лучше использовать двусвязный список для этой проблемы.

Структура узла: 

struct node {
    int data;
    struct node *next;
    struct node *prev;
};

Метод: 

void reverse() {

    struct node *temp = head; // assuming you have the head node as a global variable.
    struct node *lastPtr = head;

    for (int i = 0; i < len; i++) { // assuming you have length as a global variable.
        lastPtr = lastPtr->next;
    }

    for (int i = 0; i < len / 2; i++) {
        temp->data += lastPtr->data;
        lastPtr->data = temp->data - lastPtr->data;
        temp->data -= lastPtr->data;
        temp = temp->next;
        lastPtr = lastPtr->prev;
    }
}
...