CareerCup

void rev(struct node **head)
{
struct node*a=*head,*b=NULL,*c;
while(a!=NULL)
{
c=b;
b=a;
a=a->next;
b->next=c;
}
*head=b;
}

//recursive
void rev(struct node**head)
{
struct node *first,*rest;
first=*head;
rest=first->next;
if(rest==NULL)
return;
rev(&rest);
first->next->next=first;
first->next=NULL;
*head=rest;
}

What do you mean by reverse a linked list with single pointers then double pointers?

I would check the 3 rows and 3 columns and then 2 diagonal lines.

iterative, single pointers:
----
node * reverse(node* head) {
node *pre = NULL;

while (head) {
node *next = head->next;
head->next = pre;
pre = head;
head = next;
}

return pre;
}

iterative, double pointers:
-----
Who has any ideas?

recursively, not tail-recursive:
------
node *reverse(node* head) {
if (!head) return NULL;
if (!head->next) return head;

node *tail = head->next;
node *newhead = reverse(head->next);
tail->next = head;
head->next = NULL;

return newhead;
}

recursively, tail-recursive:
------
node *reverse(node *head, node *pre = NULL) {
if (!head) return NULL;

node *next = head->next;

head->next = pre;
if (!next) return head;
else return (next, head);
}


What do you do if it has a loop
---------------
If the linked list has a loop, the recursive solution will not work. It runs forever until all memory is used up.
The Iterative solution will still give a result. it depends on the user's opinion whether the result is correct or not.
Generally speaking, I would think that to reverse a linked list with a loop doesn't make much sense.

what's tail-recursive,and what's not? thanks

For tail-recursive, this blog has a good explanation
http://blogs.msdn.com/chrsmith/archive/2008/08/07/understanding-tail-recursion.aspx

void ReverseLinkList()
{
NODE *pNode , *pTemp ;

cout << " REVERSE LINK LIST CALLED " << endl;
if(pHead != NULL)
{
pNode = pHead;

while(true)
{
if(pNode->pPrev == NULL)
{
cout << " HEAD " << endl;
cout << " Current Value " << pNode->nData << endl;
pNode->pPrev = pNode->pNext;
pNode->pNext = NULL;
pTail = pNode;
pNode = pNode->pPrev;
}
if(pNode->pNext != NULL)
{
cout << " Current Value " << pNode->nData << endl;
pTemp = pNode->pNext;
pNode->pNext = pNode->pPrev;
pNode->pPrev = pTemp;
pNode = pNode->pPrev;
}
if(pNode->pNext == NULL)
{
cout << " Current Value " << pNode->nData << endl;
cout << " TAIL " << endl;
pNode->pNext = pNode->pPrev;
pNode->pPrev = NULL;
pHead = pNode;
break;
}
}
cout << " OUT OF WHILE " << endl;
}
else
cout << " No element in the linklist" << endl;
}

[CODE]

void reverse(struct node **head)
{
struct node* temp = *head;
struct node* result = null;
struct node* next;

while(temp!=null)
{
next = temp->next;
temp->next = result;
result = temp;
temp = next;
}
*head = result;
return *head
}
[/CODE]

Hi,
Can anyone tell me the best way as how we can solve the first problem ? TicTacToe problem.

Thanks

Node* ptr - single pointer
Node** ptr - double pointer