c - 交换链表中的两个节点(不是节点的值)

Question

我试图编写一个函数来按链表中的值交换节点。当节点不连续时它实际上起作用。但是当我尝试交换连续节点时，我遇到了无限循环。如何解决我的代码中的这个异常问题？

#include <stdio.h>
#include <stdlib.h>

/* self-referential structure */
struct listNode {
    char data; /* each listNode contains a character */
    struct listNode *nextPtr; /* pointer to next node*/
};

typedef struct listNode ListNode; /* synonym for struct listNode */
typedef ListNode *ListNodePtr; /* synonym for ListNode* */


void swap( ListNodePtr *sPtr, char value1, char value2 )
{
    ListNodePtr previousPtr1; /* pointer to previous node whose data is value1 */
    ListNodePtr currentPtr1; /* pointer to node whose data is value1 */
    ListNodePtr previousPtr2; /* pointer to previous node whose data is value2 */
    ListNodePtr currentPtr2; /* pointer to node whose data is value2 */

    previousPtr1 = NULL;
    previousPtr2 = NULL;
    currentPtr1 = *sPtr;
    currentPtr2 = *sPtr;

    /* attempt to find the node that contains value1  */
    while( currentPtr1 != NULL && currentPtr1->data != value1 ) {
        previousPtr1 = currentPtr1;
        currentPtr1 = currentPtr1->nextPtr;
    }

    /* attempt to find the node that contains value2 */
    while( currentPtr2 != NULL && currentPtr2->data != value2 ) {
        previousPtr2 = currentPtr2;
        currentPtr2 = currentPtr2->nextPtr;
    }

    if( currentPtr1 != NULL && currentPtr2 != NULL ) { /* both of the values are found */
        if( previousPtr1 == NULL ) {
            ListNodePtr tmpPtr = currentPtr1->nextPtr;
            *sPtr = currentPtr2;
            previousPtr2->nextPtr = currentPtr1;
            currentPtr1->nextPtr = currentPtr2->nextPtr;
            currentPtr2->nextPtr = tmpPtr;
        }
        else if ( previousPtr2 == NULL ) {
            ListNodePtr tmpPtr = currentPtr2->nextPtr;
            *sPtr = currentPtr1;
            previousPtr1->nextPtr = currentPtr2;
            currentPtr2->nextPtr = currentPtr1->nextPtr;
            currentPtr1->nextPtr = tmpPtr;

        }
        else {
            ListNodePtr tmpPtr = currentPtr2->nextPtr;
            previousPtr1->nextPtr = currentPtr2;
            currentPtr2->nextPtr = currentPtr1->nextPtr;
            previousPtr2->nextPtr = currentPtr1;
            currentPtr1->nextPtr = tmpPtr;
        }
    }
    else { /* at least one of the values is not found */
        printf("Not found!\n");
    }
}
int main( void )
{
    ListNodePtr startPtr = NULL; /* initially there are no nodes */
}

显然这不是主函数的全部，有一小段代码为该函数和许多其他函数(例如此代码中的反向函数)获取输入，但我对它们没有问题。

编辑:我不想交换节点内部的值。我想交换实际节点。

Answer 1

您的问题似乎因声明不必要的变量和使用不必要的值而变得更加复杂，导致您的代码变得不必要的复杂。如果您认为您是从 ListNodePtr *sPtr 开始的，并且两个循环都根据 ListNodePtr * 值进行更改，那么您可能会意识到该算法可以是使用初始化为 sPtr 的两个变量(而不是四个)可以更好地表达，其中两个初始化为 NULL，另外两个初始化为 *sPtr。

ListNodePtr *x = sPtr,
            *y = sPtr;

while (*x != NULL && (*x)->data != value1) {
    x = &(*x)->nextPtr;
}

while (*y != NULL && (*y)->data != value2) {
    y = &(*y)->nextPtr;
}

好处有两个:

• 由于初始化为 sPtr 而不是 NULL，因此稍后您无需检查任何变量是否为 NULL (这似乎导致了决定需要交换哪些值的模糊性)。
• 现在应该更清楚需要交换哪些值，但如果不是:交换 *x 和 *y，交换 (*x)->nextPtr 和 (*y)->nextPtr。