How to swap nodes in a linked list

Overview

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

  1. Swap data within nodes.
  2. Swap nodes of the linked list.

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

Problem statement

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.

Problem explanation

Keys x=1 and y=3 are given along with the linked list whose nodes are to be swapped.

Implementation

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()

Explanation

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.

Free Resources