Swap Adjacent nodes in a Linked List Only by Manipulating pointers

Question

I am trying to swap the adjacent nodes of a linked list i.e.

1->2->3->4->5 becomes 2->1->4->3->5

My function is:

node * swapper(node * &head)
{
    if (head == NULL || head->next == NULL) return head;

    node * t = head;
    head= head->next;
    head->next = t;
    t->next = head->next;

    node *previous = head->next->next, *current = previous->next;

    while (current!=NULL&&previous!=NULL)
    {
        node * t1 = current,*t2=previous;
        current->next = previous;
        previous->next = t1->next;
        previous = t1->next;
        current = previous->next;
    }

    return head;
}

I know it can be done by swapping values but I have to do it in Constant space and without swapping the values.

I can't find why my function is not working.

Answer 1

My five cents.:)

Here is a demonstrative program that shows how to write a recursive function.

#include <iostream>
#include <functional>

struct node
{
    int data;
    struct node *next;
} *head;

void push_front( node * &head, int x )
{
    head = new node { x, head };
}

void display( node *head )
{
    for ( node *current = head; current; current = current->next )
    {
        std::cout << current->data << ' ';
    }
    std::cout << std::endl;
}

node * swapper( node * &head )
{
    if ( head && head->next )
    {
        node *tmp = std::exchange(head, head->next );
        std::exchange( tmp->next, std::exchange( tmp->next->next, tmp ) );
        swapper( head->next->next );
    }

    return head;
}

int main()
{
    const int N = 10;

    for ( int i = N; i != 0; ) push_front( head, --i );

    display( head );

    display( swapper( head ) );
}    

The program output is the following

0 1 2 3 4 5 6 7 8 9 
1 0 3 2 5 4 7 6 9 8 

Take into account that not all compilers support function std::exchange. So you will need to write it yourself.:)

If to write the main the following way

int main()
{
    const int N = 10;

    for ( int i = N; i != 0; ) push_front( head, --i );

    display( head );

    for ( node **current = &head; *current && ( *current )->next; current = &( *current )->next )
    {
        swapper( *current ); 
    }

    display( head );
}    

then the following interesting output can be obtained.:)

0 1 2 3 4 5 6 7 8 9 
1 3 5 7 9 8 6 4 2 0 

Answer 2

The first thing that I can notice is that you need to swap those two lines:

head->next = t;
t->next = head->next;

because you are saying head->next = t so you are losing the connection to the rest of the linked list.

Also, inside the loop. There are several mistakes: 1- You're changing the next of current before obtaining it in previous, which means you're losing the link (like above) 2- You're not connecting them to the nodes that are before them.

Answer 3

node * swapper(node * &head)
{
    if (head == NULL || head->next == NULL) return head;

    node * t = head;
    head= head->next;

    t->next = head->next;
    head->next = t;

    node *previous = head->next->next, *current,*parent=head->next;

    while (previous&&(current = previous->next))
    {
        node * t1 = current,*t2=previous;
        previous->next = t1->next;
        current->next = previous;
        parent->next= current;

        previous = t2->next;
        //current = previous->next;
        parent=t2;
    }

    return head;
}