Trusted answers to developer questions
Trusted Answers to Developer Questions

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

RELATED TAGS

python
RELATED COURSES

View all Courses

Keep Exploring