c - 交换双链表中的两个节点

Question

我必须编写一个程序，对链表中的节点进行排序。我需要为此作业编写 5 个函数，但我被困在其中一个函数上。我遇到问题的功能是交换两个节点。该函数的标题如下:

void swap (struct lnode** head, struct lnode* n1, struct lnode* n2)

只要两个节点不相邻，我就可以正常工作。我们提供了一个 list.h 文件，我们应该使用两个函数 evictNode(struct lnode** head, struct lnode* node) 和 void insertNode (struct lnode** head ，struct lnode* prevNode，struct lnode* nodeToBeInserted)。这些函数还处理 next 和 previous 指针的重新分配。我只是不完全确定如何交换节点(如果它们彼此相邻)。我尝试过把它画出来，但无法集中注意力。

哦，顺便说一句，我处理其余节点的方式是使用以下代码:

evictNode(head, n1);
evictNode(head, n2);
insertNode(head, n1prev, n2);
insertNode(head, n2prev, n1);

编辑:尝试

struct lnode* temp = n2;
insertNode(head,n1prev,temp)
evictNode(head, n2)

其中struct lnode* n1prev = nodeGetPrev(n1)有两个函数返回前一个/下一个指针

Answer 1

我将按如下方式进行:

struct lnode* tmp = nodeGetPrev(n1);
/*
 * Remove n1 and insert it before n2
 * note to calling nodeGetPrev(n2) after removing n1
 */
evictNode( head, n1 );
insertNode( head, nodeGetPrev(n2), n1 );
/* If n2 were before n1 and we insert n1 before n2, swap is done */
if( tmp != n2 ) {
    evictNode( head, n2 );
    insertNode( head, tmp, n2 );
}