交换链表中的两个节点（不是节点的值）

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

找到要交换的节点的位置后，只需像这样编写一个简单的交换例程-

void swap(struct listNode *a,struct listNode *b)
{
  char t=a->data;
  a->data=b->data;
  b->data=t;
}

如果您按值交换节点，则可以从中获益。只需交换值。

如果您想交换节点（不是按值）

//p-first node to be swapped
//p1-prev node of p
//r-second node to be swapped
//r1-prev node of r
// a temporay listNode *
temp=r->link;
r->link=p->link;
p->link=temp;
if(p1!=NULL)
   p1->link=r;
else
   startpointer=r;
r1->link=p;
}

Answer 2

您的问题似乎因声明不必要的变量和使用不必要的值而变得复杂，从而导致您的代码变得不必要地复杂。如果您认为您是从 ListNodePtr *sPtr 开始的，并且您的两个循环都根据 ListNodePtr * 值进行更改，那么您可能会意识到使用初始化为 [=] 的两个变量可以更好地表达该算法13=]，而不是四个，其中两个初始化为 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.

Answer 3

你已经在链表中找到了这两个值对应的地址。

  if ( cur_ptr1!=NULL && cur_ptr2!=NULL){
        int  temp_val=cur_ptr1->data ; 
         cur_ptr1->data=cur_ptr2->data ;
         cur_ptr2->data = temp_val
   }

现在链表中的两个值被交换了。

假设你有一个像

这样的节点

 |1|->|2|->|3|->|4|->|5|->|6|->NULL

现在你要交换节点 2 和 5。然后我们可以像这样更改值

 |1|->|5|->|3|->|4|->|2|->|6|->NULL

Answer 4

您还应该考虑使用预迭代器而不是 while 循环。我举个例子：

/**
* Macro for iterating over a list.
*
* Declares a new variable to hold each element of the list.
* Use this macro for iterating through the list conveniently.
* Note that this mcaro modifies the internal iterator.
* For example, the following code will go through a list of strings and print
* them to the standard output:
* @code
* void printList(List listOfStrings) {
*   LIST_FOREACH(char*, str, listOfStrings) {
*     printf("%s\n", str);
*   }
* }
* @endcode

* @param type The type of the elements in the list
* @param iterator The name of the variable to hold the next list element
* @param list the list to iterate over
*/
#define LIST_FOREACH(type,iterator,list) \
for(type iterator = listGetFirst(list) ; \
    iterator ;\
    iterator = listGetNext(list))

listGetNext 和 listGetFirst 是标准的列表获取函数。它是一个非常前卫的迭代器，但对于这种 "heavy duty" 作品，我认为它是一个足够的技术。

交换链表中的两个节点（不是节点的值）

Swapping two nodes (not values of nodes) in a linked list

c

swap

linked-list

nodes