JavaScript Program to Swap Two Elements in a Linked List
We are given a linked list and the task is to swap two elements in a linked list without disturbing their links. There are multiple ways to swap. It can be done by swapping the elements inside the nodes, and by swapping the complete nodes.
Example:
Input: list = 10 -> 11 -> 12 -> 13 -> 14 -> 15 ele1 = 11 ele2 = 14 Output: list = 10 -> 14 -> 12 -> 13 -> 11 -> 15
Below are the ways by which we can swap two elements in a linked list in JavaScript.
Table of Content
- Using Recursion
- Using Iteration
Using Recursion
The approach is to use the recursive nature of JavaScript functions to traverse the linked list and swap the elements.
Algorithm:
- Define a Node class with attributes data and next to represent each element of the linked list.
- Define a LinkedList class with a constructor to initialize the head of the linked list.
- Implement a method insert(data) to insert a new node at the end of the linked list.
- Implement a recursive method swapUtil(current, x, y):
- If the current node is null, return.
- If the data of the current node equals x, set its data to y.
- If the data of the current node equals y, set its data to x.
- Recursively call swapUtil with the next node as the current node.
- Implement a method swap(x, y):
- If x and y are the same, return.
- Call swapUtil with the head of the linked list, x, and y.
- Implement a method
printList()
to print the elements of the linked list
Example: This example shows the use of the above-explained approach.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// Function to insert a new node at
// the end of the linked list
insert(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
}
// Function to swap two elements in the
// linked list using recursion
swapUtil(current, x, y) {
if (!current) return;
if (current.data === x) {
current.data = y;
} else if (current.data === y) {
current.data = x;
}
this.swapUtil(current.next, x, y);
}
swap(x, y) {
if (x === y) return;
this.swapUtil(this.head, x, y);
}
// Function to print the linked list
printList() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
// Example usage:
const linkedList = new LinkedList();
linkedList.insert(10);
linkedList.insert(11);
linkedList.insert(12);
linkedList.insert(13);
linkedList.insert(14);
linkedList.insert(15);
console.log("Before swapping:");
linkedList.printList();
linkedList.swap(12, 14);
console.log("After swapping:");
linkedList.printList();
Output
Before swapping: 10 11 12 13 14 15 After swapping: 10 11 14 13 12 15
Time Complexity: O(n) where n is the number of nodes in the linked list.
Space Complexity: O(1) because it uses a constant amount of extra space regardless of the size of the input linked list.
Using Iteration
The approach here is to define traditional linked list structure with a Node
class representing each element and a LinkedList
class to manage the list. It iteratively traverses the list to find the nodes containing the given data values and adjusts their pointers to swap positions.
Algorithm:
- Define a Node class to represent each element in the linked list with a data field and a next pointer.
- Define a LinkedList class with a head pointer initially set to null.
- Implement an append method to add elements to the end of the linked list.
- Implement a printList method to print the elements of the linked list.
- Implement a swapNodes method that takes two data values to swap.
- Traverse the linked list to find the nodes containing the given data values.
- Swap the positions of the nodes by adjusting their next pointers and the pointers of their previous nodes.
- Print the updated list.
Example: This example shows the use of the above-explained approach.
// Node class to define the structure of
// each node in the linked list
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Linked List class to define the linked
// list and methods to operate on it
class LinkedList {
constructor() {
this.head = null;
}
// Function to add a new node at the end of the linked list
append(data) {
let newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// Function to print the linked list
printList() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
// Function to swap two elements in the linked list
swapNodes(data1, data2) {
// If both data are the same, nothing to do
if (data1 === data2) {
return;
}
let prevX = null,
currX = this.head;
while (currX && currX.data !== data1) {
prevX = currX;
currX = currX.next;
}
let prevY = null,
currY = this.head;
while (currY && currY.data !== data2) {
prevY = currY;
currY = currY.next;
}
// If either data is not present, nothing to do
if (!currX || !currY) {
return;
}
// If data1 is not the head of the linked list
if (prevX) {
prevX.next = currY;
} else {
this.head = currY;
}
// If data2 is not the head of the linked list
if (prevY) {
prevY.next = currX;
} else {
this.head = currX;
}
// Swap next pointers
let temp = currX.next;
currX.next = currY.next;
currY.next = temp;
}
}
// Example usage
let ll = new LinkedList();
ll.append(10);
ll.append(11);
ll.append(12);
ll.append(13);
ll.append(14);
ll.append(15);
console.log("Linked List Before Swapping:");
ll.printList();
ll.swapNodes(11, 14);
console.log("\nLinked List After Swapping:");
ll.printList();
Output
Linked List Before Swapping: 10 11 12 13 14 15 Linked List After Swapping: 10 14 12 13 11 15
Time Complexity: O(n) for traversing the list to find the nodes to swap and O(1) for swapping them.
Space Complexity: O(1)
Contact Us