CareerCup

void reverse(struct nodes *head)
{
	struct nodes *prev, *now, *future;
	prev = head;
	now = prev->next;
	while(now)
	{
		future = now->next;
		now->next = prev;
		prev = now;
		now = future;
	}
	head->next = NULL;
	head = prev;
	display_list(head);
}

The lists is just the items linked for one. Directions does not matter!

So easy: found the items with items->next = NULL to be at end of such lists. Then this are the beginnings of the reverse list!

^_^

For a single list, it can be solved by using three pointers in O(n).

Singly linked list...

Item* reverseList(Item* firstItem)
{
Item* previous = NULL;
Item* current = firstItem;
Item* next = current->getNext();

do
{
current->setNext(previous);
previous = current;
current = next;
next = current->getNext();
} while (next != NULL)

return current;
}

public void displayReversedLinkedList(Link currNode)
{
Link pCurrent = currNode;

if (pCurrent.pNext != null)
{
displayReversedLinkedList(pCurrent.pNext);
}
pCurrent.displayLink();
}

public class Link
{
public int iData; //data item
public double dData; //data item
public Link pNext; //ptr to next link in list

//-------------------------------------------------------------
public Link(int id, double dd)
{
iData = id;
dData = dd;
pNext = null;
}

//-------------------------------------------------------------
public void displayLink()
{
Console.WriteLine("iData = " + dData);
}
//-------------------------------------------------------------
}

struct node* ReverseList(struct node** head)
{
struct node* curr= *head;
struct node* next;
struct node* newList=NULL;

while(curr != 0)
{
next= curr->next;
curr->next= newList;
newList = curr;
curr = next;
}
*head=newList;

return *head;
}