C Puzzles

yet another place for C puzzles

Tuesday, July 19, 2005

Reverse a single linked list using single pointer iteratively and recursively


here is my solution.

____________________________________________________________________
(Recursive)
struct list * reverse_ll( struct list * head)
{
      struct list * temp = NULL;

      if ( head == NULL)
          return NULL;
      if ( head->next == NULL )
         return head;

      temp = reverse_ll ( head->next );
      head->next -> next = head;
      head->next = NULL;
      return temp;
}

int main()
{
...
   head = reverse_ll(head);
...
}
____________________________________________________________________
(Iterative)

#define pointer_swap( a, b)  ((int)(a))^=((int)(b))^=((int)(a))^=((int)(b))

struct list * reverse_ll( struct list * head)
{
   struct list * temp = NULL;
   if (head &&amp; head->next) {
        temp = head->next;
        head->next = NULL;
   } else {
        return head;
   }
   while (temp->next) {
        pointer_swap(head, temp->next);
        pointer_swap(head,temp);
   }
   temp->next = head;
   //head = temp;
   return temp;
}
____________________________________________________________________



Harish's code. Minimized version of my code.
#define pointer_swap(a,b) ((int)(a)) ^= ((int)(b)) ^= ((int)(a)) ^= ((int)(b))

struct list * reverse_ll(struct list * head)
{
   struct list * temp = NULL;

   while(head) {
       pointer_swap(temp,head->next);
       pointer_swap(temp,head);  
   }
   return temp;
}