# Linked List: Program to swap two given nodes of a linked list

Write a program to swap the positions of the two given nodes in a linked list

##### Approach

- Find the two given nodes n1 and n2 by iterating over the linked list,
- Use two pointers one pointing to n1 and other pointing to node before n1
- Again use two new pointers one pointing to n2 and other pointing to node before n2
- Check for null and if all pointers are valid, then swap the nodes and return linkedlist head

For example,

given linked list is -

1 -> 2 -> 3 -> 4 -> 5 -> 6

After swapping nodes 3 & 5, the linked list looks like

1 -> 2 -> 5 -> 4 -> 3 -> 6

##### Algorithm

- If both given nodes are equal then return
- Create two pointer say previousX and currentX, set previousX as NULL and currentX on head
- While currentX is not NULL and currentX.data not equal to first given node
- previousX = currentX
- currentX = currentX.next

- While currentY is not NULL and currentY.data not equal to second given node
- previousY = currentY
- currentY = currentY.next

- If currentX and currentY both are NULL then return (nothing to do)
- If previousX is not NULL then make previousX.next = currentY, else head = currentY
- If previousY is not NULL then make previousY.next = currentX, else head = currentX
- Create node temp and set on currentX.next
- currentX.next = currentY.next
- currentY = temp

##### Complexity

Time Complexity : O(n) , where n is the number of nodes in the linked list

Space Complexity : O(1)

##### Java Code

```
import java.util.*;
class SwapNodes{
class Node {
int data;
Node next;
Node(int d) {
this.data = d;
this.next = null;
}
}
Node head;
// creating a linked list using array
public void buildLinkedlist(int A[], int noOfNodes) {
int i;
Node temp, last;
temp = new Node(A[0]);
temp.next = null;
head = temp;
last = temp;
for (i = 1; i < noOfNodes; i++) {
temp = new Node(A[i]);
temp.next = null;
last.next = temp;
last = temp;
}
}
// printing of linkedList
public void printLinkedlist() {
List allNodesList = new ArrayList<>();
Node temp = head;
while (temp != null) {
allNodesList.add(Integer.toString(temp.data));
temp = temp.next;
}
System.out.println(String.join(" -> ", allNodesList));
}
public void swapNodes(int x, int y) {
if (x == y)
return;
Node previousX = null, currentX = head;
while (currentX != null && currentX.data != x) {
previousX = currentX;
currentX = currentX.next;
}
Node previousY = null, currentY = head;
while (currentY != null && currentY.data != y) {
previousY = currentY;
currentY = currentY.next;
}
if (currentX == null || currentY == null)
return;
if (previousX != null)
previousX.next = currentY;
else
head = currentY;
if (previousY != null)
previousY.next = currentX;
else
head = currentX;
Node temp = currentX.next;
currentX.next = currentY.next;
currentY.next = temp;
}
public static void main(String[] args) {
int[] linkedlistElements = new int[] { 1, 2, 3, 4, 5, 6};
int numberOfNodes = linkedlistElements.length;
SwapNodes ll = new SwapNodes();
ll.buildLinkedlist(linkedlistElements, numberOfNodes);
System.out.println("Given Linked List");
ll.printLinkedlist();
ll.swapNodes(3, 5);
System.out.println("Linked List after swapping given nodes");
ll.printLinkedlist();
}
}
```

##### Output

Given Linked List

1 -> 2 -> 3 -> 4 -> 5 -> 6

Linked List after swapping given nodes

1 -> 2 -> 5 -> 4 -> 3 -> 6

Thanks for feedback.