Swap in Link List

#1

How to swap nodes while using LL STL?

#2

Hey, if you are using STL list then there is no inbuilt function for swapping nodes, you can do it normally using another temp variable.

#3

By using swap(*itr1,*itr2)?
Itr1 and itr2 are iterators pointing to two different nodes
It would be really helpful if you could send me the code for it

#4

if you just want to swap the data, then it can easily be done using swap function in stl. But for swapping the links…it becomes a bit tricky . You have 4 cases to handle :

  1. x and y may or may not be adjacent.
  2. Either x or y may be a head node.
  3. Either x or y may be last node.
  4. x and/or y may not be present in linked list.

Here is the code for it

void swapNodes(struct Node **head_ref, int x, int y)
{
// Nothing to do if x and y are same
if (x == y) return;

// Search for x (keep track of prevX and CurrX
struct Node *prevX = NULL, *currX = *head_ref;
while (currX && currX->data != x)
{
prevX = currX;
currX = currX->next;
}

// Search for y (keep track of prevY and CurrY
struct Node *prevY = NULL, *currY = *head_ref;
while (currY && currY->data != y)
{
prevY = currY;
currY = currY->next;
}

// If either x or y is not present, nothing to do
if (currX == NULL || currY == NULL)
return;

// If x is not head of linked list
if (prevX != NULL)
prevX->next = currY;
else // Else make y as new head
*head_ref = currY;

// If y is not head of linked list
if (prevY != NULL)
prevY->next = currX;
else // Else make x as new head
*head_ref = currX;

// Swap next pointers
struct Node *temp = currY->next;
currY->next = currX->next;
currX->next = temp;
}

#5

thanks.
I was wondering how can we achieve this in STL?

#6

there is no function in stl to do that :slight_smile:

#7

so every-time there is some question which require swapping i have to implement LL on my own…any way thanks for your help

#8

generally using vectors is easier in questions…linked list is used very rarely