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

1. If both given nodes are equal then return
2. Create two pointer say previousX and currentX, set previousX as NULL and currentX on head
3. While currentX is not NULL and currentX.data not equal to first given node
   • previousX = currentX
   • currentX = currentX.next
4. While currentY is not NULL and currentY.data not equal to second given node
   • previousY = currentY
   • currentY = currentY.next
5. If currentX and currentY both are NULL then return (nothing to do)
6. If previousX is not NULL then make previousX.next = currentY, else head = currentY
7. If previousY is not NULL then make previousY.next = currentX, else head = currentX
8. Create node temp and set on currentX.next
9. currentX.next = currentY.next
10. 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