Labels

Saturday, July 24, 2010

Reverse a single linked list using single pointer iteratively and recursively

(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 && 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;
}
____________________________________________________________________



. 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;
}

No comments:

Post a Comment