The data in a linked list can be swapped in two ways:
In this shot, we’ll discuss the second way, the time complexity of which is .
We are given a linked list and two keys. The idea here is to change the links of the nodes in such a way that the two nodes are swapped.
Keys x=1
and y=3
are given along with the linked list whose nodes are to be swapped.
The approach here is to create two pointers for both keys that are to be swapped. Initially, we’ll traverse the linked list to search x
and y
while maintaining the previous and current pointers of x
and y
keys respectively using the searchNodes()
function.
If the value is present in the list, then swap these pointers using a temp variable in a swap()
function.
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.data != x and currentX != None:prevX = currentXcurrentX = currentX.next# search for ywhile currentY.data != y and currentY != None:prevY = currentYcurrentY = currentY.nextreturn prevX, currentX, prevY, currentY,def 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 and currentY is None:return# 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 = tempdef push(self, new_data):new_node = Node(new_data)new_node.next = self.headself.head = new_nodedef printLinkedList(self):temp = self.headwhile temp != None:print(temp.data, end=" -> ")temp = temp.nextif __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()