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

[varalu 0]

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 Xisto.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 0]

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 3]

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 3]

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

[iGuest 3]

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 3]

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 3]

Linear Linked ListsData Structures -- Linked List -- Reverse

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

-question by Bamo

[iGuest 3]

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 3]

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 3]

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 3]

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 3]

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

[iGuest 3]

Here is my two centsProgram to reverse a singly list ITERATIVELY,http://forums.xisto.com/no_longer_exists/ to reverse a linked list RECURSIVELYtechnicalypto.com/2010/03/reverse-singly-linked-list-recursively.html