交换链接列表中的节点

Question

我试图使交换节点在链接列表中的函数（swapNodes）。 这里我存储了要交换的节点的前一个和下一个地址。 但我的代码陷入了无限循环。

该代码可以作为工作代码还是错误的方法？

#include<stdio.h> 
#include<stdlib.h> 
struct Node 
{ 
    int data; 
    struct Node *next; 
}; 
void push(struct Node** head_ref, int new_data) 
{ 
    struct Node* new_node = 
     (struct Node*) malloc(sizeof(struct Node)); 

    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 


void printList(struct Node *node) 
{ 
    while(node != NULL) 
    { 
     printf("%d ", node->data); 
     node = node->next; 
    } 
} 

void swapNodes(struct Node** headr,int key1,int key2) 
{ 
    struct Node* temp1 = *headr; 
    struct Node* temp2 = *headr; 

    if(key1 == key2) 
    return; 

    struct Node* prev1 =NULL; 
    struct Node* next1 =temp1; 
    while(temp1->data !=key1 && next1 !=NULL) 
    { 
    prev1 =temp1; 
    temp1 =temp1->next; 
    next1 =temp1->next; 
    } 
    struct Node* prev2 =NULL; 
    struct Node* next2 =temp2; 
    while(temp2->data !=key2 && next2 !=NULL) 
    { 
    prev2 =temp2; 
    temp2 =temp2->next; 
    next2 =temp2->next; 
    } 
    if(next1 == NULL||next2 == NULL) 
    return; 

    prev1->next =temp2; 
    temp2->next =next1; 
    prev2->next =temp1; 
    temp1->next =next2; 
} 
int main() 
{ 
    struct Node *start = NULL; 

    push(&start, 7); 
    push(&start, 6); 
    push(&start, 5); 
    push(&start, 4); 
    push(&start, 3); 
    push(&start, 2); 
    push(&start, 1); 

    printf("\n Linked list before calling swapNodes() "); 
    printList(start); 

    swapNodes(&start, 4, 3); 

    printf("\n Linked list after calling swapNodes() "); 
    printList(start); 

    return 0; 
} 

Answer 1

你应该重写你swapNodes功能位：

void swapNodes(struct Node** headr, int key1, int key2) 
{ 
    struct Node* temp1 = *headr; 
    struct Node* temp2 = *headr; 

    if(key1==key2) 
     return; 

    struct Node* prev1=NULL; 
    while(temp1 && temp1->data!=key1) 
    { 
     prev1=temp1; 
     temp1=temp1->next; 
    } 
    struct Node* prev2=NULL; 
    while(temp2 && temp2->data!=key2) 
    { 
     prev2=temp2; 
     temp2=temp2->next; 
    } 

    if(temp1==NULL || temp1==NULL) 
     return; 

    // temp1 is a head 
    if (prev1 == NULL) { 
     *headr = temp2; 
    } else { 
     prev1->next = temp2; 
    } 

    // temp2 is a head 
    if (prev2 == NULL) { 
     *headr = temp1; 
    } else { 
     prev2->next = temp1; 
    } 

    struct Node *buff = temp2->next; 
    temp2->next = temp1->next; 
    temp1->next = buff; 
} 

正如你可以看到你不需要next1和next2指针。但是您必须检查temp1或temp2是否是头：当您需要将头替换为另一个节点时，这是一种特殊情况。其余的很简单 - 只需通过缓冲节点交换节点即可。

Answer 2

函数具有未定义的行为，因为它没有考虑到，例如headr可以等于或NULL和prev1prev2可以等于NULL。

编写一个函数可以找到与给定数据相对应的节点。

尽管如此，函数swapNodes可以写成以下方式。它找到要交换的节点，然后将指针交换到节点及其数据成员next。

给你

void swap(struct Node **first, struct Node **second) 
{ 
    struct Node *tmp = *first; 
    *first = *second; 
    *second = tmp; 
} 

void swapNodes(struct Node **headr, int key1, int key2) 
{ 
    if (key1 == key2) return; 

    struct Node **first = headr; 

    while (*first && (*first)->data != key1) first = &(*first)->next; 

    if (*first == NULL) return; 

    struct Node **second = headr; 

    while (*second && (*second)->data != key2) second = &(*second)->next; 

    if (*second == NULL) return; 

    swap(first, second); 
    swap(&(*first)->next, &(*second)->next); 
} 

这里是一个示范项目。

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

struct Node 
{ 
    int data; 
    struct Node *next; 
}; 

void push(struct Node** head_ref, int new_data) 
{ 
    struct Node* new_node = 
     (struct Node*) malloc(sizeof(struct Node)); 

    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 

void printList(struct Node *node) 
{ 
    while(node != NULL) 
    { 
     printf("%d ", node->data); 
     node = node->next; 
    } 
} 

void swap(struct Node **first, struct Node **second) 
{ 
    struct Node *tmp = *first; 
    *first = *second; 
    *second = tmp; 
} 

void swapNodes(struct Node **headr, int key1, int key2) 
{ 
    if (key1 == key2) return; 

    struct Node **first = headr; 

    while (*first && (*first)->data != key1) first = &(*first)->next; 

    if (*first == NULL) return; 

    struct Node **second = headr; 

    while (*second && (*second)->data != key2) second = &(*second)->next; 

    if (*second == NULL) return; 

    swap(first, second); 
    swap(&(*first)->next, &(*second)->next); 
} 

int main(void) 
{ 
    struct Node *start = NULL; 

    push(&start, 7); 
    push(&start, 6); 
    push(&start, 5); 
    push(&start, 4); 
    push(&start, 3); 
    push(&start, 2); 
    push(&start, 1); 

    printf("\n Linked list before calling swapNodes() "); 
    printList(start); 

    swapNodes(&start, 4, 3); 

    printf("\n Linked list after calling swapNodes() "); 
    printList(start); 

    return 0; 
} 

它的输出是

Linked list before calling swapNodes() 1 2 3 4 5 6 7 
Linked list after calling swapNodes() 1 2 4 3 5 6 7 

事实上功能swapNodes因为它是写（没有一个单独的函数，用于查找节点对于给定的数据）做两件事情：它1）发现两个节点和它2）交换它们。搜索节点可能不成功。所以函数应该向用户报告节点是否被交换。在这种情况下，最好将函数声明为返回类型为int。

例如

int swapNodes(struct Node **headr, int key1, int key2) 
{ 
    int success = key1 != key2; 

    if (success) 
    {   
     struct Node **first = headr; 
     struct Node **second = headr; 

     while (*first && (*first)->data != key1) first = &(*first)->next; 

     success = *first != NULL; 

     if (success) 
     {    
      while (*second && (*second)->data != key2) second = &(*second)->next; 

      success = *second != NULL; 
     } 

     if (success) 
     {    
      swap(first, second); 
      swap(&(*first)->next, &(*second)->next); 
     } 
    } 

    return success; 
} 

如果写一个单独的函数，因为它是上面那么该交换节点将看起来更清晰和更简单的功能提到搜索的节点。

例如

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

struct Node 
{ 
    int data; 
    struct Node *next; 
}; 

void push(struct Node** head_ref, int new_data) 
{ 
    struct Node* new_node = 
     (struct Node*) malloc(sizeof(struct Node)); 

    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 

void printList(struct Node *node) 
{ 
    while(node != NULL) 
    { 
     printf("%d ", node->data); 
     node = node->next; 
    } 
} 

void swap(struct Node **first, struct Node **second) 
{ 
    struct Node *tmp = *first; 
    *first = *second; 
    *second = tmp; 
} 

struct Node ** find(struct Node **headr, int data) 
{ 
    while (*headr && (*headr)->data != data) headr = &(*headr)->next; 

    return headr; 
} 

void swapNodes(struct Node **first, struct Node **second) 
{ 
    swap(first, second); 
    swap(&(*first)->next, &(*second)->next); 
} 

int main(void) 
{ 
    struct Node *start = NULL; 

    push(&start, 7); 
    push(&start, 6); 
    push(&start, 5); 
    push(&start, 4); 
    push(&start, 3); 
    push(&start, 2); 
    push(&start, 1); 

    printf("\n Linked list before calling swapNodes() "); 
    printList(start); 

    struct Node **first; 
    struct Node **second; 

    if ((first = find(&start, 4)) && (second = find(&start, 3))) swapNodes(first, second); 

    printf("\n Linked list after calling swapNodes() "); 
    printList(start); 

    return 0; 
}