交換鏈接列表中的節點

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; 
}