Key takeaways:
Swapping nodes in a linked list involves updating links (pointers) rather than swapping values.
A linked list consists of nodes, each with data and a pointer to the next node.
To swap nodes, find the nodes and their previous nodes, then adjust the “next” pointers.
If swapping involves the head node, update the head pointer to the new head.
The process works for any two nodes, even if they are not adjacent.
Time complexity is O(n) due to traversal for locating nodes, and space complexity is O(1).
Efficient node swapping is crucial for algorithms like sorting and reversing linked lists.
The data in a linked list can be swapped in two ways:
Swap data within nodes.
Swap nodes of the linked list.
Swapping nodes in a linked list is a common operation useful in various algorithms and problems, such as sorting and reversing the list. Unlike arrays or lists in other programming languages, linked lists are not contiguous in memory. Therefore, when swapping nodes, we must manipulate the links (pointers) between them rather than simply swapping the values.
This Answer explains how to swap nodes in a singly linked list using a few approaches and examples.
A linked list is a linear data structure made up of nodes, with each node containing two components:
Data: Stores the value or data of the node.
Next pointer: Points to the next node in the sequence.
A singly linked list has a single pointer from one node to the next, while a doubly linked list has two pointers—one pointing to the next node and one pointing to the previous node.
In a singly linked list, to swap two nodes, we must:
Locate the nodes to be swapped.
Adjust the pointers of the adjacent nodes to point to the correct swapped nodes.
Swapping the nodes involves three steps:
Updating the pointers of the previous nodes.
Adjusting the “next” pointers of the nodes themselves.
Updating the head pointer if the nodes to be swapped are the first or last nodes.
Let’s consider an example with a singly linked list:
Head -> 1 -> 2 -> 3 -> 4 -> 5
Let’s say we want to swap the nodes with values 1 and 3.
Start with the head node.
Locate the nodes to be swapped. Here, 1 and 3.
We need to find the previous nodes of the nodes we want to swap, i.e., the nodes before 1 and 3. In this case, NULL is the previous node to 1, and 2 is the previous node to 3.
The node before 1 (which is NULL) should now point to the node with value 3.
The node before 3 (which is 2) should now point to the node with value 1.
The next pointer of 1 should point to the node that follows 3 (which is 4).
The next pointer of 3 should point to the node that follows 1 (which is 2).
After swapping:
Head -> 3 -> 2 -> 1 -> 4 -> 5
Here is a C++ implementation of how to swap two nodes in a singly linked list.
class Node:# Creating a nodedef __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef searchNodes(self, x, y):currentX = currentY = self.headprevX = prevY = None# search for xwhile currentX and currentX.data != x:prevX = currentXcurrentX = currentX.next# search for ywhile currentY and currentY.data != y:prevY = currentYcurrentY = currentY.nextreturn prevX, currentX, prevY, currentYdef swap(self, x, y):# both keys are same or null, do nothingif x == y:returnprevX, currentX, prevY, currentY = self.searchNodes(x, y)if currentX is None or currentY is None:return # x or y not found in the list# x is not headif prevX is not None:prevX.next = currentYelse:# make y as headself.head = currentY# y is not headif prevY is not None:prevY.next = currentXelse:# make x as headself.head = currentX# swap remaining pointerstemp = currentX.nextcurrentX.next = currentY.nextcurrentY.next = temp# Ensure the last node points to Noneif currentX.next is None:currentX.next = Noneif currentY.next is None:currentY.next = Nonedef push(self, new_data):new_node = Node(new_data)new_node.next = self.headself.head = new_nodedef printLinkedList(self):temp = self.headwhile temp:print(temp.data, end=" -> ")temp = temp.nextprint("Null") # To mark the end of the listif __name__ == '__main__':linked_list = LinkedList()# Assign data valueslinked_list.push(5)linked_list.push(4)linked_list.push(3)linked_list.push(2)linked_list.push(1)# Print the linked list dataprint('Before Swap: ')linked_list.printLinkedList()linked_list.swap(1, 3)# Print the linked list dataprint('\nAfter Swap: ')linked_list.printLinkedList()
Lines 3–5: Node.__init__(self, data)
Initializes a node with the given data.
Sets the next pointer to None.
Lines 7–9: LinkedList.__init__(self)
Creates an empty linked list with the head set to None.
Prepares the structure to hold and manipulate nodes.
Lines 11–25: searchNodes(self, x, y)
Finds nodes containing values x and y, along with their previous nodes.
Returns the previous and current nodes for both values.
Lines 27–54: swap(self, x, y)
Swaps two nodes with values x and y by adjusting their next pointers.
Updates the head pointer if one of the nodes is the head.
Lines 56–59: push(self, new_data)
Adds a new node with new_data at the start of the linked list.
Updates the head to the newly added node.
Lines 61–65: printLinkedList(self)
Traverses the linked list and prints the data of each node.
Outputs the structure of the linked list in a readable format.
To further enhance your knowledge and skills in coding interviews, we recommend a specially designed path, Educative-99. This path offers interactive lessons that give hands-on experience with coding problems and opportunities to test and refine your solutions.
Time complexity: The time complexity is n is the number of nodes in the linked list. This is because we need to traverse the list twice (once to find each node to swap).
Space complexity: The space complexity is
Haven’t found what you were looking for? Contact Us