12 replies to this topic

[varalu]

Give an algorithm to reverse a linked list with a time complexity of O(n) and minimal space complexity.

What is a linked list?
Search trap17.com. i Have already answered this question in one of my older questions.


Solution 1
Here is one simple solution...

Void ReverseList(node* head)
{
	node *temp,*current,*result;
	temp=null;
	result=null;
	current=head;
	while(current!=null)
	{
		temp=current->next;
		current->next=result;
		result=current;
		current=temp;
	}
   head=result;

The above was suggested by my friend. But i guess we still have some problems in the above code and can be refined more.
Do post back with better ideas and solutions.

[pointybirds]

There aren't too many simpler iterative algorithms than the one you've given. I would perhaps have the function return a result:

Node *reverse(Node *head) {
   Node *curr=head, *prev=NULL, *next;

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

[iGuest]

i think this will serve better
Data Structures -- Linked List -- Reverse

Replying to pointybirds

NODE* revlist(NODE *head)
{
NODE *tmp=NULL, *tmp1=NULL;
while (head != NULL)
{
tmp = head;
head = head->next;
tmp->next = tmp1;
tmp1 = tmp;
}
return head;
}


-reply by raja

[iGuest]

Replying to Trap FeedBackerYou are returning NULL, set head to tmp first.

[iGuest]

1.Give an example in which there is the implimentation of copy constructor and assignment operator an string should be there.

2. Why static method don't have this pointer?

-question by prangya

[iGuest]

simple linked list
Data Structures -- Linked List -- Reverse

/*
* Simple operations on linked list. If any problem
* please mail to me jagannath_pattar@yahoo.Co.In
*/

#include <stdio.H>

/*
* Data structure used, its simple :)
*/
Typedef struct linked_list_s
{
int value;
struct linked_list_s *next;
}linked_list_t;

/*
* Add a node at the end of the list.
*/
Linked_list_t* add_node(linked_list_t *head, int value)
{
linked_list_t *newNode = NULL;
linked_list_t *node = head;
linked_list_t *prev = head;

newNode = (linked_list_t *)calloc(1, sizeof(linked_list_t));
newNode->value = value;

while(node)
{
prev = node;
node = node->next;
}
if(prev == node)
return newNode;

prev->next = newNode;

return head;
}

/*
* delete a specified node from the list.
*/
Linked_list_t* delete_node(linked_list_t *head, int value)
{
linked_list_t *node = NULL;
linked_list_t *prev = NULL;

for(node = head; node != NULL; prev = node, node = node->next)
{
if(node->value == value)
{
//Check for head node modification
if(prev == NULL)
{
head = head->next;
free(node);
return head;
}

prev->next = node->next;
free(node);
return head;
}
}
return head;
}

/*
* display all the nodes of the list.
*/
Void list_nodes(linked_list_t *head)
{
linked_list_t *node = head;
printf("nHead");
while(node)
{
printf("->%d ",node->value);
node = node->next;
}
printf("->NULLand");
}


/*
* Display all the nodes in reverse order withoout modifying list.
*/
Void list_nodes_in_reverse_order(linked_list_t *head)
{
linked_list_t *end = NULL;
linked_list_t *node = NULL;

printf("nReverse Head");
while(head != end)
{
node = head;
while(node->next != end)
node = node->next;

printf("->%d ",node->value);
end = node;
}
printf("->NULLand");
}


/*
* Reversing the linked list with recursion; I recommond this method..
*/
Linked_list_t* reverse_with_recursion_anotherway(linked_list_t* current, linked_list_t* parent)
{
linked_list_t* revhead = NULL;

if(current == NULL)
revhead = parent;
else
{
revhead = reverse_with_recursion_anotherway(current->next, current);
current->next = parent;
}
return revhead;
}

/*
* Reversing the linked list;
*/
Linked_list_t* reverse_with_recursion(linked_list_t* node)
{
linked_list_t* temp = NULL;

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

temp = reverse_with_recursion(node->next);
temp->next =node;
return node;
}

/*
* reversing linked list without recursion.
*/
Linked_list_t* reverse_without_recursion(linked_list_t* head)
{
linked_list_t* prevNode = NULL;
linked_list_t* currNode = head;
linked_list_t* nextNode = head->next;

while(currNode)
{
currNode->next = prevNode;
prevNode = currNode;
if(nextNode == NULL)
break;
currNode = nextNode;
nextNode = nextNode->next;
}
return currNode;
}

/*
* main program, which displays menu for maitaining linked list.
*/
Main()
{
int choice = -1;
int value = 0;
linked_list_t *head = NULL;
linked_list_t *node = NULL;

do
{
printf("and what you wanna do?and");
printf("1. Add a node and");
printf("2. Delete a node and");
printf("3. List all nodes and");
printf("4. Reverse (without recursion) the list and");
printf("5. Reverse (recursively) the list and");
printf("6. Reverse (recursively) another wayand");
printf("7. Just display in reverse orderand");
printf("8. Exit and");
scanf("%d",&choice);

switch(choice)
{
case 1:
printf("nEnter value: ");
scanf("%d",&value);
head = add_node(head, value);
break;

case 2:
printf("nEnter value: ");
scanf("%d",&value);
head = delete_node(head, value);
break;

case 3:
list_nodes(head);
break;

case 4:
node = head;
head = reverse_without_recursion(head);
break;

case 5:
node = head;
while(node->next)
node = node->next;
head = reverse_with_recursion(head);
head->next = NULL;
head = node;
break;

case 6:
head = reverse_with_recursion_anotherway(head, NULL);
break;

case 7:
list_nodes_in_reverse_order(head);
break;

case 8:
exit(0);
break;
}
}while(1);
}


-reply by jagannath

[iGuest]

Linear Linked ListsData Structures -- Linked List -- Reverse

How to reverse a linear linked list without using a temporaly variable.

-question by Bamo

[iGuest]

Singly Linked Linear List(SLLL) and Doubly Linked Linear List(DLLL)Data Structures -- Linked List -- Reverse

Write an Algorithm to reverse a SLLL and DLLL.

-question by Bamo

[iGuest]

linked list reverse and memoryData Structures -- Linked List -- Reverse

in the some of your funntions when returning the memory becomes null

head->value=ok

head->next becomes null after function exit

==============

void ReverseList(LISTP* head)

{

LISTP *temp,*current,*result;

temp=NULL;

result=NULL;

current=head;

while(current!=NULL)

{

temp=current->next;

current->next=result;

result=current;

current=temp;

}

head=result;

}

===================

 

if I print hte list inside the function it is ok

void display_list(LISTP* listp)

{

LISTP* temp=listp;

while(temp->next!=NULL)

{

printf("%dand",temp->data);

temp=temp->next;

}

}

======================

 

but if I exit the function the next pointer becomes null , I suppoise the solution is using static pointer allocated outside the function ... 

any way my idea

==========

void reverselist(LISTP* listp)

{

LISTP* next = (LISTP*)malloc(sizeof(LISTP));

LISTP* next_of_next = (LISTP*)malloc(sizeof(LISTP));

next=listp->next;

if(next!=NULL)

next_of_next = next->next;

listp->next = NULL;

while(next_of_next!=NULL)

{

next->next=listp;

listp=next;

next=next_of_next;

next_of_next=next_of_next->next;

}

 

display_list(listp);

//free(next);   ???  is nneeded

//free(next_of_next);  is needed

}

-reply by michael

Keywords: reverse linked list

[iGuest]

stack codesData Structures -- Linked List -- Reverse

hi there guys...Can you help me in my simple problem?

how was the codes in reversing a name using stacks?

just like this...M a r I c h u

then the output will be like this one...U h c I r a m

thanks for your help.,in advance!

-question by mharie_chue

[iGuest]

linked listData Structures -- Linked List -- Reverse

I need to show a full program of each linked list

I.E 1.Singly linked list

  2.Doubly linked list

  3. Circular  linked list

  4. Circular doubly linked list

-reply by sintay

 

[iGuest]

Data Structures -- Linked List -- Reverse - Reverse a linked listData Structures -- Linked List -- Reverse

//The right solution...typedef struct elementT{ Int value; Struct elementT *next; }element;void reverse(element **head) { element *current=*head,*result=NULL,*temp=NULL; while(current!=NULL) { temp=current->next; current->next=result; result=current; current=temp; } *head=result; }