Замена узлов в одном связанном списке

Question

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

Вот что я написал до сих пор:

void swapNode(call * &head, call * &first, call * &second){
    call * firstPrev = NULL;
    call * secPrev = NULL;
    call * current = head;

    //set previous for first
    while((current->next != first) ){
        current = current->next;
    }

    firstPrev = current;
    current = head;

    //set previous for second
    while((current->next != second) ){
        current = current->next;
    }

    secPrev = current;
    current = second->next;

    //set firstPrev-> next to second
    firstPrev->next = second;
    //set secPrev->next to first
    secPrev->next = first;
    //set second->next = first->next
    second->next = first->next;
    //set first->next to current
    first->next = current;

    current = head;
    while(current->next != NULL){
        cout << current->number << endl;
        current = current->next;
    }

    cout << current->number << endl;
}

EDIT: Теперь у меня есть это как часть подкачки, но она все еще не работает правильно

//swap firstPrev-> next with second->next
tmp = firstPrev->next;
second->next = firstPrev->next;
second->next = tmp;
//swap swap first->next with second->next
tmp = first->next;
second->next = first->next;
second->next = tmp;

EDIT2: Похоже, этот тоже не работает, у меня ошибка с сегом.

    //swap previous's->next
    tmp =firstPrev->next;
    secPrev->next = firstPrev->next;
    secPrev->next = tmp;
    //swap swap first->next with second->next
    tmp = first->next;
    second->next = first->next;
second->next = tmp;

Answer 1

Скажем, у нас есть:

Node1 -> Node2 -> Node3 -> Node4 -> Node5

Чтобы поменять местами два узла, вам необходимо поменять значения next единиц перед каждым из них, а также значения next узлов, которые вы хотите поменять.

Таким образом, чтобы поменять местами, скажем, Node2 и Node3, вам нужно поменять местами Node1->next с Node2->next и Node2->next с Node3->next. Это будет работать, даже если они находятся рядом друг с другом (или даже если это один и тот же узел). Например:

Своп Node1->next и Node2->next

Node1->next = Node3
Node2->next = Node2

Обмен Node2->next с Node3->next

Node2->next = Node4
Node3->next = Node2

Это выглядит как:

Node1 -> Node3 -> Node2 -> Node4 -> Node5

Перевернуто!

Как отмечалось в разделе комментариев, если поменять местами Node1, вам нужно будет установить новый заголовок для связанного списка.

---

В ответ на редактирование вопроса:

Ваш код для обмена почти верно. Однако вам нужно поменять firstPrev на secPrev. Так случилось в моем примере, что мы дважды меняли одно из значений next узла, потому что они были рядом друг с другом. Но логически мы хотим поменять next с двух предыдущих, а затем поменять next с реальных узлов. Попробуйте это:

//swap firstPrev-> next with secPrev->next
tmp = firstPrev->next;
secPrev->next = firstPrev->next;
secPrev->next = tmp;
//swap swap first->next with second->next
tmp = first->next;
second->next = first->next;
second->next = tmp;

Если вы получаете segfault, проверьте переменную tmp - это может быть ошибка размещения или удаления где-то. Где вы взяли segfault?

Answer 2

В большинстве реальных сценариев обмен значениями будет лучшим решением:

void swapNode(call * &head, call * &first, call * &second) {
    // swap values, assuming the payload is an int:
    int tempValue = first->value;
    first->value = second->value;
    second->value = tempValue;
}

Если это не разрешено, то вы хотите сделать аналогичный стиль в разделе -> next вместо компонента -> value. А затем выполните другой обмен на компоненты firstPrev-> next и secondPrev-> next. Не упустите особый случай, когда первая или вторая == голова.

Answer 3

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

int swapNode( node *&head * &first, node * &second)
{
     //first we will declare the 
     //previous of the swapping nodes
     node *firstprev=NULL;
     node*secprev=NULL;
     node*current=head;
     //set previous first
     while(current->next!=first)
     {
        current=current->next;
     }
     firstprev=current;
     //seting 2nd previous
     while(current->next!=second)
     {
        current=current->next;
     }

    // swap values, assuming the payload is an int:
    int tempValue = first->value;
    first->value = second->value;
    second->value = tempValue;
    //swaping next of the nodes
    firstprev->next=second;
    secprev->next=first;
    return; 
}

Answer 4

Здесь p1 - 1-й узел, подлежащий обмену, p2 - 2-й узел, подлежащий обмену. И prevnode - это узел, предшествующий p2

        temp=head;
        while(temp!=NULL){
        if(temp->link==p1){
           temp->link=p2;

           prevnode->link=p2->link; 
           p2->link=p1->link;
           t=p1->link;
           while(t!=prevnode)
              t=t->link;
              cout<<" YES";
           cout<<"["<<t->num<<"] ";
           p1->link=prevnode->link;
           prevnode->link=p1;   

           temp=p1;
        }//if_

        cout<<" "<<temp->num;              
        temp=temp->link;   
    }

Answer 5

Практическое правило: «Всегда отделяйте данные от указателей и никогда не меняйте указатели, только данные!». Сделайте swap явным без использования memcpy (), чтобы избежать проблем с выравниванием. Это не приводит к снижению производительности с точки зрения алгоритмической сложности, но делает ваш код более читабельным и безопасным.

Answer 6

Спасибо всем за ваши ответы! Я понимаю, что этот вопрос задавался почти два года назад, и ответ давно принят, но ответы меня немного смутили. Таким образом, несмотря на то, что спрашивающий, вероятно, не заботится о новых ответах, я хотел бы добавить свою версию, на случай, если другие читатели также будут смущены, и задокументировать мой собственный подход. Кое-что из этого могло бы быть более подходящим в качестве комментариев, но у меня пока нет репутации комментировать.

Во-первых, независимо от того, как часто я смотрю на это - на доске или в отладчике - я не могу избежать окончания цикла в первом узле, то есть указывать на себя, если я не использую условное выражение для различать случаи, когда узлы являются смежными и нет, даже с помощью абстрактных шагов или конкретного кода из принятого в настоящее время ответа Smashery. Я немного осмотрелся в Интернете, чтобы найти код в стиле принятого в настоящее время ответа, чтобы избежать такого условия, но для меня это удивительно сложно избежать, и мои поиски не дали такого решения (если я не ошибаюсь о предложенном, возможно, неправильном). Если бы существовало какое-нибудь умное выражение, которое могло бы дать адрес первого узла, когда они смежные, и адрес преемника первого узла, когда их нет, то это условное условие не понадобилось бы, потому что выяснение нового преемника второго узла - это то, что (очевидно) требует это условно.

Во-вторых, у меня тот же вопрос о последовательных присвоениях тех же переменных в принятом ответе, что и у других комментаторов. Я надеюсь, что я здесь не слишком плотный, но присваиваю разные значения одной и той же переменной последовательно, если, возможно, не в случае побочных эффектов, мне просто никогда не кажется, что переменная имеет какое-либо другое значение, кроме последнего присваивания, независимо от того, какую конфигурацию узлов я рассматриваю, и, таким образом, делает предыдущие назначения явно избыточными. Если я ошибаюсь по этому поводу и этот подход фактически решит эту проблему, то я смог бы устранить последнее условие в приведенном ниже коде, от которого я пытался избавиться, когда впервые искал в Интернете решение для замена узлов без специального корпуса соседних узлов. Я не совсем уверен, но это звучало так, как будто Smashery преднамеренно оставил эти повторяющиеся задания из логической строгости и чтобы лучше проиллюстрировать процедуру - хотя, возможно, я неправильно понял.

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

Однако я признаю, что это может зависеть от семантики контейнера. Для массива можно ожидать, что метод подкачки изменит значение под ссылками на определенный индекс этого массива. Это будет означать, что ссылки предназначены не для ссылки на конкретный объект, а на позицию в контейнере, которую можно проиндексировать. Если мы рассмотрим связанный список как средство для упорядочивания только набора объектов, которые используются вне связанного списка, пользователь, вероятно, ожидает, что операция подкачки будет обмениваться только позицией, а не содержимым.

Представьте, например, что связанный список представляет объекты типа "автомобиль". У каждого автомобиля есть владелец, и этот владелец ссылается на свой автомобиль через указатель на него. Теперь предположим, что связанный список представляет собой порядок обслуживания автомобилей, которые планируется обслужить для проверки в автосалоне. Если бы мы поменялись местами содержимого двух узлов, чтобы обменять слоты расписания на две машины, и сделали это путем обмена их содержимым, то обслуживание фактически произошло бы в новом, правильном порядке - но люди также в конечном итоге внезапно приобрели бы разные машины! (Я бы не против поменяться с Tesla, потому что я только за рулем Corolla.)

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

Наконец, к коду. Как я уже говорил выше, мне не удалось избежать специального кожуха для соседних узлов.

Во-первых, определение вспомогательного метода:

int find_node(int v, node* root, node** n, node** pn) {
    int i = 0;
    for (*n = root; *n != NULL && (*n)->v != v; ++i) {
        *pn = *n;
        *n = (*n)->next;
    }
    return i;
}

Этот метод находит узел по его значению. Возвращаемое целое число - это позиция, начинающаяся с нуля (если хотите, назовите ее индексом) узла в связанном списке. Я обнаружил, что обнаружение смежности через положение, а не сравнение указателей, более читабельно Начало списка - root. Метод устанавливает n, чтобы указать на узел, содержащий переданное значение. В pn метод сохраняет предшественника n.

Ниже приведен фактический своп:

void swap_nodes(node **root, int v1, int v2) {
    if (v1 == v2) return;

    node *n1, *n2, *pn1, *pn2;

    int p1 = find_node(v1, *root, &n1, &pn1);
    int p2 = find_node(v2, *root, &n2, &pn2);

    if (p1 > p2) {
        std::swap(n1, n2);
        std::swap(pn1, pn2);
        std::swap(p1, p2);
    }

    if (p1 == 0) *root = n2; 
    else pn1->next = n2;

    node* nn1 = n1->next;
    n1->next = n2->next;

    if (p2 - p1 > 1) {
        n2->next = nn1;
        pn2->next = n1;
    } else {
        n2->next = n1;
    }
}

Извините, что немного изменил сигнатуру метода ОП. Я обнаружил, что удобнее передавать значения узлов для обмена, а не указатели узлов. Если вы передадите указатели на узлы только на соответствующие узлы, вам придется выполнить другой обход, чтобы найти предшественников с этим решением, что показалось мне немного неловким. Если мы не можем различить узлы по этим значениям, например, значения не уникальны, однако нам понадобятся указатели на узлы.

Как и в объяснении для find_node выше, мы сначала находим позиции, узлы и предшественники для значений узлов, передаваемых в swap_nodes через v1 и v2. Все значения для первого и второго узлов меняются местами, если второй узел, который нужно поменять, появляется перед первым. Для этого не так много кода, он сокращает специальный регистр и упрощает визуализацию.

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

Предыдущее значение преемника первого узла необходимо запомнить, если узлы не являются соседними. Затем преемник первого узла устанавливается текущим преемником второго узла. Это единственное изменение, которое применяется ко всем случаям: новый преемник первого узла, являющийся старым преемником второго узла, является единственной уверенностью и полезен для начала, чтобы запомнить операции с указателями и их последовательность при реализации этого обмена .

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

Answer 7

void swap()
{
 struct node *temp=0,*nxt,*ptr;
 ptr=head;
 int count=0;
 while(ptr)
 {
   nxt=ptr->link;
   if(nxt)
 {
  if(count==0)
    head=nxt;
    count++;
   ptr->link=nxt->link;
   nxt->link=ptr;
   if(temp!=NULL)
   temp->link=nxt;
   temp=ptr;
   if(ptr->link==NULL)
   break;
   ptr=nxt->link->link;
 }

} }

Answer 8

Если вы хотите знать все методы обмена двумя узлами в связанных списках только на простом C, перейдите по этой ссылке:

http://sahilalipuria.wordpress.com/2013/01/21/swapping-two-nodes-of-a-singly-linked-lists-set-2/

Answer 9

Хотя я не уверен на 100%, что ответ должен включать ссылки на указатель узла (или указатели на указатели), и это должно затем обрабатывать случай, когда один из узлов также является главой списка.

void swapNodes(node *&first, node *&second)
{
  node *t = second->next;
  second->next = first->next;
  first->next = t;
  t = second;
  second = first;
  first = t;
}

Тогда вы можете назвать это, например:

swapNodes(head, secPrev->next);

или

swapNodes(firstPrev->next, head);

или

swapNodes(firstPrev->next, secPrev->next)

и он должен работать автоматически.

EDIT:

swapNodes может быть еще более читабельным:

void swapNodes(node *&first, node *&second)
{
  std::swap(first->next, second->next);
  std::swap(first, second);
}