C语言如何在不交换数据的情况下交换链表中的节点？

Question

我使用了这个排序功能，但我不知道如何交换节点地址而不是值。我使用双向链表。

谢谢

void sort(LISTnode **h) {
    LISTnode * start, * min, * temp;
    int num;
    start = *h;
    while (start->next != NULL) {
        temp = start;
        min = temp;
        temp = temp->next;

        while (temp != NULL) {
            if (temp->number < min->number)
                min = temp;
                temp = temp->next;
        }

        // This part of the code
        num = min->number;
        min->number = start->number;
        start->number = num;

        start = start->next;
    }    
}

Answer 1

交换两个节点（编辑：non-adjacent 一个！ - 需要特殊处理，因为下面的代码将设置部分涉及的 next/prev 指针到相邻节点上自己的 object!!!):

x->prev->next = y;
x->next->prev = y;

y->prev->next = x;
y->next->prev = x;

现在节点在列表中的位置发生了变化，需要自己调整节点：

tmp = x->prev;
x->prev = y->prev;
y->prev = tmp;

tmp = x->next;
x->next = y->next;
y->next = tmp;

最后：调整头指针：

if(list->head == x)
{
    list->head = y;
}
else if(list->head == y)
{
    list->head = x;
}

完成...

好吧，只有一半：以上适用于双重和循环链表（您可以通过 list->head->previous 获得尾巴）。如果您没有循环链表，请将适当的空指针检查添加到第一个代码部分（第二个您不需要，假设 x 和 y 都不为空...）并对尾部进行头部调整，也是。

旁注：由于必须调整头部（和尾部，如果需要），如果没有 parent 节点列表，您将无法安全交换...

不过，需要进行大量的指针调整。我宁愿考虑在节点内交换数据（尽管在您的问题中被明确排除！）。如果由于数据很大而不想这样做，请考虑将数据与节点分开存储，并让节点有一个指向数据的指针。交换就是交换两个指针，你甚至不需要 parenting 列表 object...

Answer 2

替代方法..
使用双指针交换指针比使用指针更容易..

void swap(Node* &a,Node* &b){
    Node* c=a,a=b,b=c;
}

void swapNodes(Node** head_ref, int x, int y)
{
    Node**a=NULL,**b=NULL;
    Node* head=*head_ref;
    while(head!=NULL){
        if(head->data==x)   *a=head;
        else if(head->data==y)  *b=head;
    }  
    if(a&&b){
        swap(*a,*b);
        swap((*a)->next,(*b)->next);
    }
}

C语言如何在不交换数据的情况下交换链表中的节点？

How to swap nodes in a linked list without swapping data in C language?

c

swap

linked-list

nodes

doubly-linked-list