Trusted answers to developer questions

Naba Ali

The data in a linked list can be swapped in two ways:

- Swap data within nodes.
- Swap nodes of the linked list.

In this shot, we’ll discuss the second way, the time complexity of which is $O(n)$.

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 node def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def searchNodes(self, x, y): currentX = currentY = self.head prevX = prevY = None # search for x while currentX.data != x and currentX != None: prevX = currentX currentX = currentX.next # search for y while currentY.data != y and currentY != None: prevY = currentY currentY = currentY.next return prevX, currentX, prevY, currentY, def swap(self, x, y): # both keys are same or null, do nothing if x == y: return prevX, currentX, prevY, currentY = self.searchNodes(x, y) if currentX is None and currentY is None: return # x is not head if prevX is not None: prevX.next = currentY else: # make y as head self.head = currentY # y is not head if prevY is not None: prevY.next = currentX else: # make x as head self.head = currentX # swap remaining pointers temp = currentX.next currentX.next = currentY.next currentY.next = temp def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node def printLinkedList(self): temp = self.head while temp != None: print(temp.data, end=" -> ") temp = temp.next if __name__ == '__main__': linked_list = LinkedList() # Assign data values linked_list.push(5) linked_list.push(4) linked_list.push(3) linked_list.push(2) linked_list.push(1) # Print the linked list data print('Before Swap: ') linked_list.printLinkedList() linked_list.swap(1, 3) # Print the linked list data print('\nAfter Swap: ') linked_list.printLinkedList()

There are three cases in swapping of node:

`Case 1:`

Line 29-30: If the content of both x and y are the same, then return.`Case 2:`

Line 37-42: If “x” is not the head node, point the current node of Y to the current node of X. Otherwise, make Y as a new head node.`Case3:`

Line 44-49: If “y” is not the head node, point the current node of X to the current node of Y. Otherwise, make X as a new head node.- Line 52-54: Now, swap the currentX and currentY using temp variable.

RELATED TAGS

python

CONTRIBUTOR

Naba Ali

RELATED COURSES

View all Courses

Keep Exploring

Related Courses