**Reverse a linked list using only 2 pointers.**

This question has created quite an interest in many students and has been asked many times.

So i thought i give a discussion on the underlying techniques to do it.

**Some preliminary requirements**

1. Swap two variables without using temporary variables.

easy:

a = a+b

b = a-b

a = a-b

problems:

integer overflow problem

addition overhead involved

solution using xor

a = a xor b

b = a xor b

a = a xor b

fastest way is to write it in one line

a = a ^ b ^ (b=a)

2. Cyclic swap of three variables a ,b ,c

using temporary variable

temp=a

a=b

b=c

c=temp

using two swaps

swap(a,b)

swap(b,c)

solution using xor

a = a^b^c

b = a^b^c

c = a^b^c

a = a^b^c

solution in one line

c = a ^ b ^ c ^ (a=b) ^ (b=c)

because of symmetry a,b,c can be in any order and all the statements below are valid

b = a ^ b ^ c ^ (c=a) ^ (a=b)

a = a ^ b ^ c ^ (b=c) ^ (c=a)

__Reverse a linked list using 2 pointers.__

Students usually go for recursion when they hear such question of optimizing variables.

Well this can be done interatively. However few special conditions need to be taken in mind.

Algorithm:

let

**a1 -> a2 -> a3 -> .... -> an**be a linked list
An intermediate step involved in reversing the list given below where the list is divided into two parts, reversed and non-reversed.

**a1 <- a2 <- ... ak-1**

**<-**

**ak(p)**

**(q)ak+1 -> ..... -> an**

p is the head of the reversed linked list. p=ak

q is the head of non-reversed linked list. q=ak+1

the next step in the reversing process would be

**a1 <- a2 <- ... ak <- ak+1(p) (q)ak+2 -> ..... -> an**

p=ak+1

q=ak+2

which can basically be summarised as

t = q->next

q->next=p

p=q;

q=t

which is very similar to the cyclic swap.

so in one line

**q = p ^ q ^ q->next ^ (q->next=p) ^ (p=q)**

**And this is the only way of doing it.**

you may think that just like in cyclic swap all the variables are independend and using symmetry you may replace the above statement as

p = p ^ q ^ q->next ^ (q = q->next) ^ (q->next=p) [ incorrect ]

invalid because q becomes q->next and hence the now q->next is actually old q->next->next...thus is invalid

q->next = p ^ q ^ q->next ^ (p=q) ^ (q=q->next) [ incorrect ]

here too the final assignment done to q->next is not the old q->next because q has already changed.

Both the statements have logical error in them.

**A small test program**

struct List

{

int info;

List * next;

};

int main()

{

int a[] = { 1 , 2 , 3 , 4 , 5 };

List *head=NULL,*p=NULL,*q;

//create a linked list

q = new List;

q->info=a[0];

q->next=NULL;

head = p = q;

for(int i=1; i<5; i++)

{

q = new List;

q->info=a[i];

q->next=NULL;

p->next=q;

p=q;

}

//display the list

p = head;

while(p)

{

cout<<info<<" ";

p = p->next;

}

cout<<endl;

//reverse the list

p=head;

q=p->next;

p->next=NULL;

while(q)

{

q = (List*) ((int)p ^ (int)q ^ (int)q->next ^ (int)(q->next=p) ^ (int)(p=q));

}

head = p;

//display the list

p = head;

while(p)

{

cout<<info<<" ";

p = p->next;

}

cout<<endl;

}

Great work Sir! Keep Posting such tutorials

ReplyDeletesir if you are doing c = a ^ b ^ c ^ (a=b) ^ (b=c) then answer may depend on the situation in which a =b was called first or b = c . I think this code has a bug of sequence point . correct me if I am wrong

ReplyDeletewell according to g++/gcc the sequence is correct.

Deletec = a^b^c ^ (b=c) ^ (a=b) is wrong.

for other compilers the answer may vary.

thanks ashish! very creative and nice solution to the problem. also a good read:

ReplyDeletereverse linked list java