Related Tags

python

# How to swap nodes in a linked list

Naba Ali

## 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)$.

### 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

def __init__(self):

def searchNodes(self, x, y):
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

if  prevX is not None:
prevX.next = currentY
else:

if  prevY is not None:
prevY.next = currentX
else:

# swap remaining pointers
temp = currentX.next
currentX.next = currentY.next
currentY.next = temp

def push(self, new_data):
new_node = Node(new_data)

while temp != None:
print(temp.data, end=" -> ")
temp = temp.next

if __name__ == '__main__':

# Assign data values
# Print the linked list data
print('Before Swap: ')

# Print the linked list data
print('\nAfter Swap: ')


### 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.

RELATED TAGS

python

CONTRIBUTOR

Naba Ali
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time 