Programa de Python para intercambiar Nodes en una lista vinculada sin intercambiar datos

Dada una lista enlazada y dos claves en ella, intercambie Nodes por dos claves dadas. Los Nodes deben intercambiarse cambiando los enlaces. El intercambio de datos de Nodes puede ser costoso en muchas situaciones cuando los datos contienen muchos campos. 

Se puede suponer que todas las claves de la lista enlazada son distintas.

Ejemplos: 

Input : 10->15->12->13->20->14,  x = 12, y = 20
Output: 10->15->20->13->12->14

Input : 10->15->12->13->20->14,  x = 10, y = 20
Output: 20->15->12->13->10->14

Input : 10->15->12->13->20->14,  x = 12, y = 13
Output: 10->15->13->12->20->14

Esto puede parecer un problema simple, pero es una pregunta interesante ya que tiene que manejar los siguientes casos. 

1. xey pueden o no ser adyacentes.
2. Cualquiera de los dos, x o y, puede ser un Node principal.
3. O x o y puede ser el último Node.
4. x y/oy pueden no estar presentes en la lista enlazada.

Cómo escribir un código de trabajo limpio que maneje todas las posibilidades anteriores.

La idea es buscar primero x e y en la lista enlazada dada. Si alguno de ellos no está presente, entonces regrese. Mientras busca x e y, realice un seguimiento de los punteros actuales y anteriores. Primero cambie el siguiente de los punteros anteriores, luego cambie el siguiente de los punteros actuales. 

A continuación se muestra la implementación del enfoque anterior. 

# Python program to swap two given nodes
# of a linked list
class LinkedList(object):
    def __init__(self):
        self.head = None
 
    # Head of list
    class Node(object):
        def __init__(self, d):
            self.data = d
            self.next = None
 
    # Function to swap Nodes x and y
    # in a linked list by changing links
    def swapNodes(self, x, y):
 
        # Nothing to do if x and y are
        # the same
        if x == y:
            return
 
        # Search for x (keep track of
        # prevX and CurrX)
        prevX = None
        currX = self.head
        while currX != None and currX.data != x:
            prevX = currX
            currX = currX.next
 
        # Search for y (keep track of
        # prevY and currY)
        prevY = None
        currY = self.head
        while currY != None and currY.data != y:
            prevY = currY
            currY = currY.next
 
        # If either x or y is not present,
        # nothing to do
        if currX == None or currY == None:
            return
 
        # If x is not head of linked list
        if prevX != None:
            prevX.next = currY
 
        else:  # make y the new head
            self.head = currY
 
        # If y is not head of linked list
        if prevY != None:
            prevY.next = currX
        else: 
 
            # make x the new head
            self.head = currX
 
        # Swap next pointers
        temp = currX.next
        currX.next = currY.next
        currY.next = temp
 
    # Function to add Node at beginning
    # of list.
    def push(self, new_data):
 
        # 1. alloc the Node and put the data
        new_Node = self.Node(new_data)
 
        # 2. Make next of new Node as head
        new_Node.next = self.head
 
        # 3. Move the head to point to new Node
        self.head = new_Node
 
    # This function prints contents of
    # linked list starting from the given Node
    def printList(self):
        tNode = self.head
        while tNode != None:
            print tNode.data,
            tNode = tNode.next
 
# Driver code
llist = LinkedList()
 
# The constructed linked list is:
# 1->2->3->4->5->6->7
llist.push(7)
llist.push(6)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
print "Linked list before calling swapNodes() "
llist.printList()
llist.swapNodes(4, 3)
print "
Linked list after calling swapNodes() "
llist.printList()
# This code is contributed by BHAVYA JAIN

Producción:

Linked list before calling swapNodes() 1 2 3 4 5 6 7 
Linked list after calling swapNodes() 1 2 4 3 5 6 7 

Complejidad de tiempo : O(n)

Espacio Auxiliar : O(1)

Optimizaciones: el código anterior se puede optimizar para buscar x e y en un solo recorrido. Se utilizan dos bucles para mantener el programa simple. 

Enfoque más simple:

# Python3 program to swap two given
# nodes of a linked list
 
# A linked list node class
class Node:
 
    # constructor
    def __init__(self, val = None,
                 next1 = None):
        self.data = val
        self.next = next1
 
    # Print list from this
    # to last till None
    def printList(self):
        node = self
 
        while (node != None):
            print(node.data, end = " ")
            node = node.next
        print(" ")
 
# Function to add a node
# at the beginning of List
def push(head_ref, new_data):
 
    # Allocate node
    (head_ref) = Node(new_data, head_ref)
    return head_ref
 
def swapNodes(head_ref, x, y):
    head = head_ref
 
    # Nothing to do if x and y are same
    if (x == y):
        return None
 
    a = None
    b = None
 
    # Search for x and y in the linked list
    # and store their pointer in a and b
    while (head_ref.next != None):
 
        if ((head_ref.next).data == x):
            a = head_ref
 
        elif ((head_ref.next).data == y):
            b = head_ref
 
        head_ref = ((head_ref).next)
 
    # If we have found both a and b
    # in the linked list swap current
    # pointer and next pointer of these
    if (a != None and b != None):
        temp = a.next
        a.next = b.next
        b.next = temp
        temp = a.next.next
        a.next.next = b.next.next
        b.next.next = temp
 
    return head
 
# Driver code
start = None
 
# The constructed linked list is:
# 1.2.3.4.5.6.7
start = push(start, 7)
start = push(start, 6)
start = push(start, 5)
start = push(start, 4)
start = push(start, 3)
start = push(start, 2)
start = push(start, 1)
 
print("Linked list before calling swapNodes() ")
start.printList()
start = swapNodes(start, 6, 1)
print("Linked list after calling swapNodes() ")
start.printList()
# This code is contributed by Arnab Kundu

Producción:

Linked list before calling swapNodes() 1 2 3 4 5 6 7 
Linked list after calling swapNodes() 6 2 3 4 5 1 7 

Complejidad de tiempo : O(n)

Espacio Auxiliar : O(1)

Consulte el artículo completo sobre Intercambiar Nodes en una lista vinculada sin intercambiar datos para obtener más detalles.