link list question

[panfilero]

Hello, I was looking for some help in manipulating a linked list. I'm not looking for code so much as I am looking for a way to approach the problem.

I have a linked list, where the nodes each have a number as a member, lets say 4,3,1,2 and what i want to do is rearrange it to a linked list that follows the asceding order pattern... 1,2,3,4

I'm confused on how I might do this, how I could move my pointer along the linked list, compare values and rearrange them

I was thinking that i could somehow compare the members containing the number, then copy the max one to a temporary sturcture, then nsomehow free it from my linked list and push the new structre intol a new linked list....


Im having trouble developing an algorithm for this, can anybody help me.... Thank you very much

[itsme86]

You shouldn't need to do any copying of structures. Sorting the linked list should only require relinking of the nodes. If you find a node that needs to be moved you'd just do something like:

1) Make the moving node's previous node point to the moving node's next node.
2) Make the moving point's next node point to the insertpoint node.
3) Make the insertpoint's previous node point to the moving node.

So take: a -> c -> b -> d...call b the moving node and c the insertpoint.
1) a -> c -> d (now b is not in the list, c->next points to d instead of b)
2) a -> c -> d, b -> c (b still can't be accessed by walking the list, but b->next points to c)
3) a -> b -> c -> d (now a->next points to b and b->next points to c...you're done)

The code might look like:

moving->prev->next = moving->next;
moving->next = insertpoint->next;
insertpoint->prev->next = moving;

If you're working with a singly-linked list (you don't have a prev pointer) you'll need to keep track of the previous nodes as you're walking the list. You'll also need to make sure of things like the insertpoint isn't the beginning of the list, in which case the prev pointer won't be valid.

[cbastard]

If You dont wanna do it by moving pointers.
then sort the linklist just like you do for arrays.
just go through the list and swap adjacent member values like you do for bubble sort
Now you will traverse like curr=curr->next as you do i++.