Swapping nodes in linked list

Question

I tried to make function(swapNodes) for swapping nodes in linked list. Here i stored previous and next addresses of nodes which are to be swapped. But my code stucked in infinite loop.

Can this code be made as working one or it is a wrong approach?

#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

The function has undefined behavior because it does not take into account that for example headr can be equal to NULL or prev1 and prev2 can be equal to NULL.

It would be good to write one more function that finds the node that corresponds to the given data.

Nevertheless the function swapNodes can be written the following way. It finds nodes to be swapped and then swaps pointers to the nodes and their data members next.

Here you are

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

Here is a demonstrative program.

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

Its output is

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

In fact the function swapNodes as it is written (without a separate function that finds nodes for a given data) does two things: it 1) finds two nodes and it 2) swaps them. Searching of the nodes can be unsuccessful. So the function should report to the user whether nodes were swapped. In this case it is desirable to declare the function as having return type int.

For example

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

If to write a separate function that searches a node as it was mentioned above then the function that swaps nodes will look more clear and simpler.

For example

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

Answer 2

You should rewrite you swapNodes function a bit:

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

As you can see you don't need next1 and next2 pointers. But you must check if temp1 or temp2 is a head: it is a special case when you need to replace head with another node. The rest is trivial - just swap nodes via buffer node.