Programa de Python para intercambiar el Node Kth desde el principio con el Node Kth desde el final en una lista vinculada

Dada una lista enlazada individualmente, intercambie el k-ésimo Node desde el principio con el k-ésimo Node desde el final. No se permite el intercambio de datos, solo se deben cambiar los punteros. Este requisito puede ser lógico en muchas situaciones en las que la parte de datos de la lista enlazada es enorme (por ejemplo, la línea de detalles del estudiante Nombre, RollNo, Dirección, etc.). Los punteros siempre son fijos (4 bytes para la mayoría de los compiladores). Ejemplo:

Input: 1 -> 2 -> 3 -> 4 -> 5, K = 2
Output: 1 -> 4 -> 3 -> 2 -> 5 
Explanation: The 2nd node from 1st is 2 and 
2nd node from last is 4, so swap them.

Input: 1 -> 2 -> 3 -> 4 -> 5, K = 5
Output: 5 -> 2 -> 3 -> 4 -> 1 
Explanation: The 5th node from 1st is 5 and 
5th node from last is 1, so swap them.

Ilustración:

Enfoque: La idea es muy simple: encuentre el k-ésimo Node desde el principio y el k-ésimo Node desde el último es n-k+1-ésimo Node desde el principio. Intercambia ambos Nodes. 
Sin embargo, hay algunos casos de esquina, que deben ser manejados

  1. Y está al lado de X
  2. X está al lado de Y
  3. X e Y son iguales
  4. X e Y no existen (k es más que el número de Nodes en la lista vinculada)

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

Python3

"""
A Python3 program to swap kth node from 
the beginning with kth node from the end
"""
class Node:
    def __init__(self, data, 
                 next = None):
        self.data = data
        self.next = next
      
class LinkedList:
    def __init__(self, *args, **kwargs):
        self.head = Node(None)
  
    """
    Utility function to insert a node at 
    the beginning
    @args:
        data: value of node
    """
    def push(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node
      
    # Print linked list
    def printList(self):
        node = self.head
  
        while node.next is not None:
            print(node.data, end = " ")
            node = node.next
      
    # count number of node in linked list
    def countNodes(self):
        count = 0
        node = self.head
        while node.next is not None:
            count += 1
            node = node.next
        return count
      
    """
    Function for swapping kth nodes from
    both ends of linked list
    """
    def swapKth(self, k):
  
        # Count nodes in linked list
        n = self.countNodes()
  
        # Check if k is valid
        if n<k:
            return
  
        """
        If x (kth node from start) and 
        y(kth node from end) are same 
        """
        if (2 * k - 1) == n:
            return
  
        """
        Find the kth node from the beginning of 
        the linked list. We also find previous 
        of kth node because we need to update 
        next pointer of the previous. 
        """
        x = self.head
        x_prev = Node(None)
        for i in range(k - 1):
            x_prev = x
            x = x.next
  
        """
        Similarly, find the kth node from end 
        and its previous. kth node from end 
        is (n-k + 1)th node from beginning 
        """
        y = self.head
        y_prev = Node(None)
        for i in range(n - k):
            y_prev = y
            y = y.next
  
        """
        If x_prev exists, then new next of it 
        will be y. Consider the case when y->next 
        is x, in this case, x_prev and y are same. 
        So the statement "x_prev->next = y" creates 
        a self loop. This self loop will be broken
        when we change y->next. 
        """
        if x_prev is not None:
            x_prev.next = y
  
        # Same thing applies to y_prev
        if y_prev is not None:
            y_prev.next = x
          
        """
        Swap next pointers of x and y. These 
        statements also break self loop if 
        x->next is y or y->next is x 
        """
        temp = x.next
        x.next = y.next
        y.next = temp
  
        # Change head pointers when k is 1 or n
        if k == 1:
            self.head = y
          
        if k == n:
            self.head = x
  
# Driver Code
llist = LinkedList()
for i in range(8, 0, -1):
    llist.push(i)
llist.printList()
  
  
for i in range(1, 9):
    llist.swapKth(i)
    print("Modified List for k = ", i)
    llist.printList()
    print("")
# This code is contributed by Pulkit

Producción:

Original Linked List: 1 2 3 4 5 6 7 8

Modified List for k = 1
8 2 3 4 5 6 7 1

Modified List for k = 2
8 7 3 4 5 6 2 1

Modified List for k = 3
8 7 6 4 5 3 2 1

Modified List for k = 4
8 7 6 5 4 3 2 1

Modified List for k = 5
8 7 6 4 5 3 2 1

Modified List for k = 6
8 7 3 4 5 6 2 1

Modified List for k = 7
8 2 3 4 5 6 7 1

Modified List for k = 8
1 2 3 4 5 6 7 8

Análisis de Complejidad:

  • Complejidad temporal: O(n), donde n es la longitud de la lista. 
    Se necesita un recorrido de la lista.
  • Espacio Auxiliar: O(1). 
    No se requiere espacio adicional.

¡ Consulte el artículo completo sobre Intercambiar el Node Kth desde el principio con el Node Kth desde el final en una lista vinculada para obtener más detalles!

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *