how to swap with pointers ?

[surrealtrauma]

if i have circular linked list like:
14->12->10->8->6->4->2->0->//

how can i revises it as
0->2->4->6->8->10->12->14->//

is there any other method besides swap?
Thank you

 

[Karl Heinz Buchegger]

if i have circular linked list like:
14->12->10->8->6->4->2->0->//

how can i revises it as
0->2->4->6->8->10->12->14->//

is there any other method besides swap?

What's wrong with swap
(By the way: what so you want to swap)

There are lots of ways you can reverse such a thing.
It all depends on your actual implementation of that linked
list. Eg. if the whole thing is implemented as a doubly linked
list, then swapping the previous pointer with the next pointer
for all list elements does the trick nicely.

 

[Ioannis Vranos]

if i have circular linked list like:
14->12->10->8->6->4->2->0->//

how can i revises it as
0->2->4->6->8->10->12->14->//

is there any other method besides swap?

Perhaps making it double-link?

 

[Fraser Ross]

If its a doubly-linked list the reverse algorithm will do. If its
singularly linked a multiple step method might be needed using reverse_copy.

Fraser.

 

[osmium]

if i have circular linked list like:
14->12->10->8->6->4->2->0->//

how can i revises it as
0->2->4->6->8->10->12->14->//

is there any other method besides swap?

You might push everything onto a stack and then pop it and rebuild the list
(or make a new one).

 

[surrealtrauma]

it must be maintain as a circular linked list.

 

[Pete Becker]

:




You might push everything onto a stack and then pop it and rebuild the list
(or make a new one).

No need for a stack. Just remove the head element and insert it at the
head of the new list. Repeat until done.

 

[Kai-Uwe Bux]

if i have circular linked list like:
14->12->10->8->6->4->2->0->//

how can i revises it as
0->2->4->6->8->10->12->14->//

is there any other method besides swap?
Thank you

Probably, you are talking about the following idiom to reverse a single
linked list in place:


template < typename T >
class slist_node {
public:

T data;
slist_node * next;

};

template< typename T >
slist_node<T>* reverse_slist( slist_node<T> * & head ) {
slist_node<T> * prev = 0;
while ( head != 0 ) {
// want to cyclicly permute the values of the variables
// head -> prev -> head->next -> head.
// cycle realized via two transpositions:
std::swap( prev, head->next );
std::swap( head, prev );
}
return( prev );
}



Now, of course, you could realize the cyclic permutation directly:

template< typename T >
slist_node<T>* reverse_slist( slist_node<T> * & head ) {
slist_node<T> * prev = 0;
while ( head != 0 ) {
// want to cyclicly permute the values of the variables
// head -> prev -> head->next -> head.
// explicity cycle:
slist_node<T> * dummy = head->next;
head->next = prev;
prev = head;
head = dummy;
}
return( prev );
}


However, an optimizing compiler would likely produce identical code for
both solutions. I do not know of any more efficient way to reverse a list.


Best

Kai-Uwe Bux

 

[Karl Heinz Buchegger]

it must be maintain as a circular linked list.

Those 2 are not mutually exclusive.
A circular linked list can be a doubly linked list.

circular: tail node is connected with the head node
double linked: each node contains pointers to the next
and previous node.

So there is nothing that prevents a circular linked list
to be double linked.