Search code examples
clinked-listswapxor

xor linked list swap 2 nodes C

I'm trying to swap 2 nodes with a XOR linked list

my struct : 

typedef struct s_node
{
    struct s_node *ptr;
    int data;
} t_node;

and my function (where I want to swap x and y) a is the prev of x and b the next of y

void swap_node(t_node *a, t_node *x, t_node *y, t_node *b)
{
   //Swapping
   x->ptr = xor_node(y, b);
   y->ptr = xor_node(x, a);

   //Update
   a->ptr = xor_node(xor_node(y, a->ptr), y);
   b->ptr = xor_node(xor_node(x, b->ptr), x);
}

xor_node just makes a XOR on 2 t_node*.

For test, I made a list that looks like : 1 - 2 - 3 - 4

After calling this function the result is like : 1 - 2 - 2 - 1

But, I want to have : 1 - 3 - 2 - 4

Thank you!

Solution

  • I understood

    The trick is :

    for to get the next of a is : XOR(a->ptr, x) and for the prev of b is XOR(b->ptr, y)

    so 

    a->ptr = xor_node(xor_node(y, a->ptr), x);
b->ptr = xor_node(xor_node(x, b->ptr), y);