# Linked List - Swapping Nodes

• 10-01-2012
Mentallic
I'm trying to implement a selection sort algorithm on linked lists, and the trouble I've ran into is swapping any two nodes in the linked list.

My selection sort function:

Code:

```void selSortLL(NodeT *head) {     NodeT *cur = NULL;     NodeT *move = NULL;     NodeT *min = NULL;         if (head == NULL || head->next == NULL) {         return head;     }         for (cur = head; cur->next != NULL; cur=cur->next) {         min = cur;         for (move = cur->next; move != NULL; move=move->next) {             if (move->value < min->value) {                 min = move;             }         }         if (min != cur) {             //SWAP CUR W/ MIN NODES         }     }         return head; }```
I'm sure I'd need at least one temporary node, but even then I'm still unsure about how I'm going to tackle this problem.
• 10-01-2012
laserlight
Consider a few scenarios and list out what you need to do to perform the swap in each of them.
• 10-01-2012
Mentallic
Ok well if I have a situation where each of the nodes I'm swapping are not adjacent to each other or at the ends of the list, then if the nodes are a and b, it'll be something like this:

... -> a- -> a -> a+ -> ... -> b- -> b -> b+ -> ...

And so if I let a = tmp1, b = tmp2, each way I try to rearrange the links, I'm always going to break the list. I just can't wrap my head around this.
• 10-01-2012
laserlight
Quote:

Originally Posted by Mentallic
if I have a situation where each of the nodes I'm swapping are not adjacent to each other or at the ends of the list (...) each way I try to rearrange the links, I'm always going to break the list

Give the nodes nice names with a concrete example, e.g.,
A -> B -> C -> D -> E -> F

So, you want to swap B and E such that you end up with:
A -> E -> C -> D -> B -> F

Hence:
• A's next pointer must be changed to point to E
• B's next pointer must be changed to point to F
• D's next pointer must be changed to point to B
• E's next pointer must be changed to point to C

From the above list, it is immediately clear what nodes you need to have on hand in order to modify where their next pointer points to.
• 10-01-2012
Mentallic
Quote:

Originally Posted by laserlight
Give the nodes nice names with a concrete example, e.g.,
A -> B -> C -> D -> E -> F

So, you want to swap B and E such that you end up with:
A -> E -> C -> D -> B -> F

Hence:
• A's next pointer must be changed to point to E
• B's next pointer must be changed to point to F
• D's next pointer must be changed to point to B
• E's next pointer must be changed to point to C

From the above list, it is immediately clear what nodes you need to have on hand in order to modify where their next pointer points to.

Ahh thanks for that. So I do need to have tmp1=B and tmp2=E nodes but I need to change my code so that I can also have access to A and D.