成对给出链表交换节点对，C ++解决方案

问题说明：

给定一个链表，每隔两个相邻节点交换一次并返回其头部。

例：

Given 1->2->3->4, you should return the list as 2->1->4->3.

我们可以通过2种解决方案解决上述问题。

1. 迭代式
2. 递归的

根据问题，我们需要使用恒定空间来解决它。如果我们使用递归解，则每次进行递归调用时，我们将在线性时间内占据n / 2个空间。因此，我们不会解决它。

让我们研究迭代解决方案中涉及的步骤：

考虑如下所示的初始列表：

如我们所见，节点b指向节点c。如果我们使节点b指向节点a，则节点c的地址将丢失。

因此，我们将节点c的地址保存在一个临时变量中。

然后我们交换两个节点，节点a和节点b，然后将节点a指向节点d。即温度>next.

然后，在更改节点c和节点d之前，温度将指向节点e。然后我们将更改节点c和节点d。

注意：

如果有给定的对，则临时指针应始终指向下一个节点。

C解决方案

在我们的迭代解决方案中，我们采用4个指针。

new_list_start_pointer： 这将保留新交换列表的起点。

指针_a：  该指针将保存2个节点中第一个节点的地址。例如，如果我们有2个节点“ a”和“ b”，它将保存a的地址。

指针_b： 该指针将保存2个节点中第二个节点的地址。例如，如果我们有2个节点“ a”和“ b”，它将保存b的地址。

temp_pointer： 这将保留给定对中下一个节点的地址。

/*
* File     : swap_nodes_pairwise.c
* Purpose  : Swap nodes pairwise
*/

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

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

// since we are 
void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}

struct Node* swap_node_pair_wise_iterative(struct Node *List_1)
{

    struct Node *new_list_start_pointer = NULL;
    struct Node *pointer_a = List_1; // now pointer a will point to 1st element in the pair

    //  This will hold the starting point of new swapped list. 
    //  As the starting point is the second node, we shall save that address
    new_list_start_pointer = pointer_a->next; 
    

    struct Node *pointer_b = NULL;
    struct Node *temp_pointer = NULL;
    while(1)
    {
        pointer_b = pointer_a->next; // now pointer b will point to 2nd element in the pair
        temp_pointer = pointer_b->next; // now it will hold the address of next node of given pair
        
        pointer_b->next = pointer_a; // make node b pointing to node a. Refer image 2.
    
            if(temp_pointer == NULL) // if we come at the end of the list break the loop. As pointer_a is the last node, assign it to null
            {
                pointer_a->next = NULL;
                break;
            }
            
            if(temp_pointer->next == NULL) // if we come at the end of the list break the loop. As pointer_a is the last node, assign it to null
            {
                pointer_a->next = temp_pointer;
                break;      
            }
    
        pointer_a->next = temp_pointer->next; // here node a will point to node d. Refer image 3.
        pointer_a = temp_pointer;
    
    }
return new_list_start_pointer;

}


int main()
{
    struct Node *list_1 = NULL; 

    struct Node *head_pointer_from_iterative_solution = NULL; 
    struct Node *head_pointer_from_recursive_solution = NULL; 


    insert_at_begenning(&list_1,8);
    insert_at_begenning(&list_1,7);
    insert_at_begenning(&list_1,6);
    insert_at_begenning(&list_1,5);
    insert_at_begenning(&list_1,4);
    insert_at_begenning(&list_1,3);
    insert_at_begenning(&list_1,2);
    insert_at_begenning(&list_1,1);

    printf("List 1 is\n");
    display_list(&list_1);

    


    head_pointer_from_iterative_solution = swap_node_pair_wise_iterative(list_1);
    
    printf("The result list using iterative method is\n");
    display_list(&head_pointer_from_iterative_solution);



    // head_pointer_from_recursive_solution = merge_two_sorted_lists_recursive(list_1, list_2);
    
    // printf("The result list using recursive method is\n");
    // display_list(&head_pointer_from_recursive_solution);

    return 0;
}

输出：

List 1 is
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

The result list using iterative method is
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7

该网站上可用的教程列表：