xisto Community

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

## Recommended Posts

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.

##### Share on other sites

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

##### Share on other sites

i think this will serve better

Data Structures -- Linked List -- Reverse

{

NODE *tmp=NULL, *tmp1=NULL;

while (head != NULL)

{

tmp->next = tmp1;

tmp1 = tmp;

}

}

##### Share on other sites
Replying to Trap FeedBackerYou are returning NULL, set head to tmp first.

##### Share on other sites

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

##### Share on other sites

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

*/

{

int value;

/*

* Add a node at the end of the list.

*/

{

linked_list_t *newNode = NULL;

newNode->value = value;

while(node)

{

prev = node;

node = node->next;

}

if(prev == node)

return newNode;

prev->next = newNode;

}

/*

* delete a specified node from the list.

*/

{

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)

{

free(node);

}

prev->next = node->next;

free(node);

}

}

}

/*

* display all the nodes of the list.

*/

{

while(node)

{

printf("->%d ",node->value);

node = node->next;

}

printf("->NULLand");

}

/*

* Display all the nodes in reverse order withoout modifying list.

*/

{

linked_list_t *end = NULL;

linked_list_t *node = NULL;

{

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

*/

{

if(current == NULL)

else

{

revhead = reverse_with_recursion_anotherway(current->next, current);

current->next = parent;

}

}

/*

* Reversing the linked list;

*/

{

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* prevNode = NULL;

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 *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);

break;

case 2:

printf("nEnter value: ");

scanf("%d",&value);

break;

case 3:

break;

case 4:

break;

case 5:

while(node->next)

node = node->next;

break;

case 6:

break;

case 7:

break;

case 8:

exit(0);

break;

}

}while(1);

}

##### Share on other sites
Linear Linked ListsData Structures -- Linked List -- Reverse

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

-question by Bamo

##### Share on other sites
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

##### Share on other sites
linked list reverse and memoryData Structures -- Linked List -- Reverse

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

head->next becomes null after function exit

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

{

LISTP *temp,*current,*result;

temp=NULL;

result=NULL;

while(current!=NULL)

{

temp=current->next;

current->next=result;

result=current;

current=temp;

}

}

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

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

}

Keywords: reverse linked list

##### Share on other sites
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

-question by mharie_chue

##### Share on other sites
linked listData Structures -- Linked List -- Reverse

I need to show a full program of each linked list

I.E 1.Singly linked list

3. Circular  linked list

4. Circular doubly linked list

##### Share on other sites
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; }

##### Share on other sites

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

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account