Intercambiar los primeros Nodes pares e impares desde el principio y el final de una lista enlazada

Dada una Lista Vinculada individual , la tarea es intercambiar el primer Node de valor impar desde el principio y el primer Node de valor par desde el final de la Lista Vinculada . Si la lista contiene valores de Node de una sola paridad, no se requieren modificaciones.

Ejemplos:

Entrada: 4 -> 3 -> 5 -> 2 -> 3 -> NULL
Salida: 4 -> 2 -> 5 -> 3 -> 3 -> NULL
Explicación:
4 -> 3 -> 5 -> 2 -> 3 -> NULL ===> 4 -> 2 -> 5 -> 3 -> 3 -> NULL
El primer valor impar en cualquier Node desde el principio es 3 .
El primer valor par en cualquier Node desde el final es 2 .
Después de intercambiar los dos valores de Node anteriores, la lista vinculada se modifica a 4 -> 2 -> 5 -> 3 -> 3 -> NULL.

Entrada: LL: 2 -> 6 -> 8 -> 2 -> NULO
Salida: 2 -> 6 -> 8 -> 2 -> NULO

Enfoque: el problema dado se puede resolver haciendo un seguimiento de la primera y la última aparición de Nodes pares e impares respectivamente e intercambiándolos. Siga los pasos a continuación para resolver el problema:

Inicialice dos variables , digamos firstOdd y firstEven , para almacenar el primer Node que tenga valores pares e impares desde el principio y el final respectivamente.
Inicialice dos variables, digamos firstOdd y firstEven (inicialmente NULL ).
Recorra la lista enlazada y realice los siguientes pasos:
- Si el valor del Node actual es impar y firstOdd es NULL , actualice el Node firstOdd al Node actual.
- De lo contrario, actualice firstEven como el Node actual.
Después de completar los pasos anteriores, si firstOdd y firstEven no son NULL , entonces intercambie los valores en ambos punteros .
Imprima la Lista vinculada modificada como la Lista vinculada resultante.

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

Python3

# Python3 program for the above approach
  
# Structure of a node
# in the Linked List
class Node:
    def __init__(self, x):
        self.val = x
        self.next = None
  
# Function to display the Linked List
def printLL(head):
  
    # Traverse until end
    # of list is reached
    while(head):
      
        # Print the value
        # stored in the head
        print(head.val, end =' ')
          
        # Move to the next of head
        head = head.next
    print()
  
# Function to swap the nodes
def swapNodes(head, even, odd):
  
    # Keeps the track of
    # prevEven and CurrEven
    prevEven = None
    currEven = head
  
    while currEven and currEven != even:
        prevEven = currEven
        currEven = currEven.next
  
    # Keeps the track of
    # prevOdd and currOdd
    prevOdd = None
    currOdd = head
  
    while currOdd and currOdd != odd:
        prevOdd = currOdd
        currOdd = currOdd.next
  
    # If list contains nodes
    # of a single parity
    if not currEven or not currOdd:
        return head
  
    # If head of the linked list
    # does not contain even value
    if prevEven:
        prevEven.next = currOdd
  
    # Make odd node the new head
    else:
        head = currOdd
  
    # If head of the linked list
    # does not contain odd value
    if prevOdd:
        prevOdd.next = currEven
  
    # Make even node the new head
    else:
        head = currEven
  
    # Swap the next pointers
    temp = currEven.next
    currEven.next = currOdd.next
    currOdd.next = temp
  
    # Return the modified Linked List
    return head
  
# Function to swap the first odd node
# from the beginning and the first even
# node from the end of the Linked List
def swapOddAndEvenNodes(head):
  
    # Find the first even node from
    # the end of the Linked List
    even = None
    curr = head
    while curr:
        if not curr.val & 1:
            even = curr
        curr = curr.next
  
    # Find the first odd node from
    # the front of the Linked List
    odd = None
    curr = head
    while curr:
        if curr.val & 1:
            odd = curr
            break
        curr = curr.next
  
    # If required odd and even
    # nodes are found, then swap
    if odd and even:
        head = swapNodes(head, even, odd)
  
    printLL(head)
  
# Function to convert given
# array into a Linked List
def linkedList(arr):
    head = None
    ptr = None
  
    # 4 -> 3 -> 5 -> 2 -> 3 -> NULL
    for i in arr:
        if not head:
            head = Node(i)
            ptr = head
        else:
            newNode = Node(i)
            ptr.next = newNode
            ptr = newNode
    return head
  
# Driver Code
  
# Given Linked List
arr = [4, 3, 5, 2, 3]
  
# Stores head of Linked List
head = linkedList(arr)
  
swapOddAndEvenNodes(head)

Producción:

4 2 5 3 3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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

Python3

Deja una respuesta Cancelar la respuesta