Reverse Linked List without temp node

[tene]

Just saw this question on interview questions list..
Anyone has the answer??

[Denis]

What do you mean? Could you provide example?

[Biju Scaria]

I dont know what you are looking for, but the below function might help:

void reverse(struct link *list)
{
if(list!=NULL)
{
reverse(list->next);
printf("%d",list->data);
}
}

[Duthomhas]

Argh, please don't use recursion on unbounded data.

/*
  Reverse a singly linked list without recursion.
  The argument may be NULL.
  Returns the new head of the list.
  Runs in linear time and with constant memory usage.
 */
node *rev( node *head ) {
  node *next;
  node *curr = head;
  node *prev = NULL;

  while (curr != NULL) {
    next       = curr->next;
    curr->next = prev;

    prev       = curr;
    curr       = next;
    }

  return prev;
  }

Use it thus:
head = rev( head );

http://www.daniweb.com/code/snippet216991.html

Hope this helps.

[firedraco]

I think OP wanted it done without a temporary node(s).

[Duthomhas]

Oops!

It is one of those "see how stupid smart my interviewee is" questions.

It is a variation on the "how to exchange two variables without a temporary" tricks. Which, in an interview, I would answer is a stupid thing to do because it makes assumptions about the underlying data & pointer/integer conversions.

To exchange two integers without a temporary, use XOR:
a ^=b, b ^= a, a ^= b;

Use at your own risk. Enjoy!

[flykobe]

head <-> tail
head+1 <-> tail-1
head+2 <-> tail-2
....

[choisum]

> I think OP wanted it done without a temporary node(s).

I only see temporary node pointers :)