Как вставить связанный список в другой связанный список?

Я хочу, чтобы написать функцию, которая позволяет мне вставить связанный список в другой связанный список в определенном положении, так что, если связанные списки были:Как вставить связанный список в другой связанный список?

list1: [1]->[2]->[3]->NULL 
list2: [4]->[5]->[6]->NULL

Тогда вызов функции:

insertList(list1, list2, 1);

модифицирует LIST1 таким образом, что:

list1 = [1]->[4]->[5]->[6]->[2]->[3]->NULL

и list2 остается неизменным и годным к употреблению.

Вот определение структуры:

struct _node { 
    int item; 
    struct _node *next; 
} 


struct _list { 
    struct _node *head; 
    struct _node *last; 
}

Вот моя попытка, которая не работает, потому что я получаю сегмы ошибки.

void insertList(struct _list *list1, struct _list *list2, int pos) { 
    assert(list != NULL && list2 != NULL); 

    int currPos = 0; 
    struct _node *curr = list1->head; 

    if (pos < 0 || pos >= numLines(list1)) { 
     abort(); 
    } 

    // traverse linked list to get to correct position 
    while (curr != NULL && currPos != pos) { 
     curr = curr->next; 
     currPos++; 
    } 

    struct _node *temp = curr->next; 
    curr->next = list2->head; 

    while (curr != NULL) { 
     curr = curr->next; 
    } 

    curr->next = temp; 

    // updating last 
    curr = list1->head; 
    while (curr != NULL) { 
     curr = curr->next; 
    } 
    list1->last = curr; 
}

источник

2016-12-24 user6005857

Я смущен. Указывает ли каждая «голова» на тот же узел или могут быть разные головы? Вы обновляете каждый 'head' для' list2', потому что теперь он является частью 'list1', поскольку вы только копируете указатели вместо данных? И где код, который обновляет указатели (хвосты) 'tail' для' list1' и 'list2'? –

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

Ваша структура 'node' сконфигурировала две вещи: узлы в середине списка (' item' и 'next') и общее начало и конец списка (' head' и 'last'). Чтобы поддерживать согласованность, каждый раз, когда вы добавляете или удаляете элемент из головы или хвоста списка, вам нужно пройти весь список, чтобы обновить указатели 'head' и' last'. Когда вы вставляете один список в другой, вам нужно обновить все указатели во вставленном списке, чтобы указать на голову и хвост списка, в который он вставлен. И т.д. Отделите два набора данных. –

while (curr != NULL) { 
    curr = curr->next; 
}

-> В этом положении currNULL является и то, что вы делаете

curr->next = temp; //NULL->next gives you seg fault.

Вы можете

while (curr->next != NULL){ 
... 
}

Вы также должны изменить последнюю часть

while (curr != NULL) { 
    curr = curr->next; 
} 
list1->last = curr; //here also curr is NULL, you need to rull the loop 
        //till curr->next!=NULL

источник

2016-12-24 19:48:02

Спасибо, но я все равно получаю seg-ошибку после внесения этих изменений. – user6005857

Для каких входов вы получаете ошибку seg? То же, что упоминалось в проблеме? –

Те же входы в примере. – user6005857

Как вставить связанный список в другой связанный список?

ответ

Смежные вопросы