Given linked list pairs swap by changing links

Question

I have a singly linked list where I get the struct Node* head, and the return value is void. I'd like to swap in pairs without copying the data.

For example, if the input is 2->4->6 then the output is 4->2->6. But if the input is 2->4->6->7 then the output is 4->2->7->6.

Here is my code but it doesn't work.

void swapPairs(struct Node *head) {
    struct Node *node;
    while (head && head->next) {
        struct Node *nxt = head->next;
        head->next = nxt->next;
        nxt->next = head;
        node->next = nxt;
        node = head;
        head = node->next;
    }
}

Answer 1

You need to pass the pointer to the head (or current) node by reference. Otherwise the function will deal with a copy of the value of the passed pointer. Changing the copy does not influence on the original pointer.

Here is a demonstrative program that shows how a function that swaps adjacent nodes can be written.

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

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

struct Node *insert( struct Node *head, size_t pos, int data )
{
    if (head == NULL || pos == 0)
    {
        struct Node *new_node = ( struct Node * )malloc( sizeof( struct Node ) );
        new_node->next = head;
        new_node->data = data;
        head = new_node;
    }
    else
    {
        head->next = insert( head->next, pos - 1, data );
    }

    return head;
}

 FILE * display( const struct Node *head, FILE *fp )
{
    for ( ; head != NULL; head = head->next )
    {
        fprintf( fp, "%d -> ", head->data );
    }
    fputs( "null\n", fp );

    return fp;
}

void swap( struct Node **current )
{
/*
    | A | -> | A | B | -> | B | C |
    head

    Step 1:
    | B |    | A | C |  | B | C |
    head

    Step 2:
    | B |   | A | C |   | B | A |
    head
*/

    //  Step 1:
    struct Node *tmp = *current;
    *current = ( *current )->next;
    tmp->next = ( *current )->next;

    //  Step 2:
    ( *current )->next = tmp;
}

void swapPairs( struct Node **head )
{
    for ( ; *head && ( *head )->next; head = &( *head )->next->next)
    {
        swap( head );
    }
}

int main()
{
    struct Node *head = NULL;
    const int N = 10;

    srand( ( unsigned int )time( NULL ) );
    for ( int i = 0; i < N; i++ )
    {
        head = insert( head, rand() %( i + 1 ), rand() % N );
    }
        
    fputc( '\n', display( head, stdout ) );

    swapPairs( &head );    

    fputc( '\n', display( head, stdout ) );
}

The program output might look like

4 -> 7 -> 8 -> 1 -> 4 -> 8 -> 9 -> 0 -> 4 -> 6 -> null

7 -> 4 -> 1 -> 8 -> 8 -> 4 -> 0 -> 9 -> 6 -> 4 -> null