Dada una lista enlazada. La tarea es segregar sus Nodes de posición par e impar de tal manera que los Nodes de posición impar aparezcan antes que los Nodes de posición par, todos los Nodes de posición par deben estar en orden inverso.
Ejemplos:
Entrada: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
Salida: 1 -> 3 -> 5 -> 6 -> 4 -> 2 -> NULL
Entrada: 1 -> 2 -> 3 -> 4 -> 5 -> NULO
Salida: 1 -> 3 -> 5 -> 4 -> 2 -> NULO
Fuente: Entrevista de Microsoft
Enfoque: se ha discutido un problema similar en el enlace dado , pero allí la parte par no se invirtió. Mantiene los puntos pares e impares de dos puntos para los Nodes actuales en posiciones pares e impares, respectivamente. Además, almacene el primer Node de la lista enlazada par para que podamos adjuntar la lista par al final de la lista impar después de que todos los Nodes pares e impares estén conectados en dos listas diferentes. Una vez que se ha separado la lista de pares, solo tenemos que invertirla. La inversión de una lista enlazada se puede encontrar aquí . Una vez que se invierta la lista par, adjúntela a la lista enlazada impar. A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Append odd position nodes
// in reverse at the end of even
// positioned nodes in a Linked List
#include <bits/stdc++.h>
using namespace std;
// Linked List Node
struct Node {
int data;
struct Node* next;
};
// A utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// Rearranges given linked list such that all even
// positioned nodes are before odd positioned
// in a reverse
Node* rearrangeEvenOdd(Node* head)
{
// Corner case
if (head == NULL)
return NULL;
// Initialize first nodes of even and
// odd lists
Node* odd = head;
Node* even = head->next;
// Remember the first node of even list so
// that we can connect the even list at the
// end of odd list.
Node* evenFirst = even;
while (1) {
// If there are no more nodes, then connect
// first node of even list to the last node
// of odd list
if (!odd || !even || !(even->next)) {
break;
}
// Connecting odd nodes
odd->next = even->next;
odd = even->next;
// If there are NO more even nodes after
// current odd.
if (odd->next == NULL) {
even->next = NULL;
break;
}
// Connecting evenevenFirs nodes
even->next = odd->next;
even = odd->next;
}
// Reversal of even linked list
Node* current = evenFirst;
Node* prev = NULL;
Node* front = NULL;
// Iterate in the complete linked list
while (current != NULL) {
front = current->next;
current->next = prev;
prev = current;
current = front;
}
evenFirst = prev;
// Attach the reversed even linked
// list to odd linked list
odd->next = evenFirst;
return head;
}
// A utility function to print a linked list
void printlist(Node* node)
{
while (node != NULL) {
cout << node->data << " -> ";
node = node->next;
}
cout << "NULL" << endl;
}
// Driver code
int main(void)
{
Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
head->next->next->next->next->next = newNode(6);
head = rearrangeEvenOdd(head);
printlist(head);
return 0;
}
Java
// Java program to Append odd position nodes
// in reverse at the end of even
// positioned nodes in a Linked List
class sol
{
// Linked List Node
static class Node
{
int data;
Node next;
};
// A utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// Rearranges given linked list such that all even
// positioned nodes are before odd positioned
// in a reverse
static Node rearrangeEvenOdd(Node head)
{
// Corner case
if (head == null)
return null;
// Initialize first nodes of even and
// odd lists
Node odd = head;
Node even = head.next;
// Remember the first node of even list so
// that we can connect the even list at the
// end of odd list.
Node evenFirst = even;
while (true)
{
// If there are no more nodes, then connect
// first node of even list to the last node
// of odd list
if (odd == null || even == null || (even.next) == null)
{
break;
}
// Connecting odd nodes
odd.next = even.next;
odd = even.next;
// If there are NO more even nodes after
// current odd.
if (odd.next == null)
{
even.next = null;
break;
}
// Connecting evenevenFirs nodes
even.next = odd.next;
even = odd.next;
}
// Reversal of even linked list
Node current = evenFirst;
Node prev = null;
Node front = null;
// Iterate in the complete linked list
while (current != null)
{
front = current.next;
current.next = prev;
prev = current;
current = front;
}
evenFirst = prev;
// Attach the reversed even linked
// list to odd linked list
odd.next = evenFirst;
return head;
}
// A utility function to print a linked list
static void printlist(Node node)
{
while (node != null)
{
System.out.print( node.data + " -> ");
node = node.next;
}
System.out.println( "null" );
}
// Driver code
public static void main(String args[])
{
Node head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(5);
head.next.next.next.next.next = newNode(6);
head = rearrangeEvenOdd(head);
printlist(head);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to Append odd position nodes
# in reverse at the end of even
# positioned nodes in a Linked List
import math
# Linked List Node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# A utility function to create a new node
def newNode(key):
temp = Node(key)
temp.data = key
temp.next = None
return temp
# Rearranges given linked list such that
# all even positioned nodes are before
# odd positioned in a reverse
def rearrangeEvenOdd(head):
# Corner case
if (head == None):
return None
# Initialize first nodes of even and
# odd lists
odd = head
even = head.next
# Remember the first node of even list so
# that we can connect the even list at the
# end of odd list.
evenFirst = even
while True:
# If there are no more nodes,
# then connect first node of
# even list to the last node
# of odd list
if (odd == None or even == None or
(even.next) == None):
break
# Connecting odd nodes
odd.next = even.next
odd = even.next
# If there are NO more even nodes after
# current odd.
if (odd.next == None):
even.next = None
break
# Connecting evenevenFirs nodes
even.next = odd.next
even = odd.next
# Reversal of even linked list
current = evenFirst
prev = None
front = None
# Iterate in the complete linked list
while (current != None):
front = current.next
current.next = prev
prev = current
current = front
evenFirst = prev
# Attach the reversed even linked
# list to odd linked list
odd.next = evenFirst
return head
# A utility function to print a linked list
def printlist(node):
while (node != None) :
print(node.data, end = "->")
node = node.next
print("NULL")
# Driver code
if __name__=='__main__':
head = newNode(1)
head.next = newNode(2)
head.next.next = newNode(3)
head.next.next.next = newNode(4)
head.next.next.next.next = newNode(5)
head.next.next.next.next.next = newNode(6)
head = rearrangeEvenOdd(head)
printlist(head)
# This code is contributed by Srathore
C#
// C# program to Append odd position nodes
// in reverse at the end of even
// positioned nodes in a Linked List
using System;
class GFG
{
// Linked List Node
public class Node
{
public int data;
public Node next;
};
// A utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// Rearranges given linked list such that
// all even positioned nodes are before
// odd positioned in a reverse
static Node rearrangeEvenOdd(Node head)
{
// Corner case
if (head == null)
return null;
// Initialize first nodes of even and
// odd lists
Node odd = head;
Node even = head.next;
// Remember the first node of even list so
// that we can connect the even list at the
// end of odd list.
Node evenFirst = even;
while (true)
{
// If there are no more nodes,
// then connect first node of
// even list to the last node
// of odd list
if (odd == null || even == null ||
(even.next) == null)
{
break;
}
// Connecting odd nodes
odd.next = even.next;
odd = even.next;
// If there are NO more even nodes after
// current odd.
if (odd.next == null)
{
even.next = null;
break;
}
// Connecting evenevenFirs nodes
even.next = odd.next;
even = odd.next;
}
// Reversal of even linked list
Node current = evenFirst;
Node prev = null;
Node front = null;
// Iterate in the complete linked list
while (current != null)
{
front = current.next;
current.next = prev;
prev = current;
current = front;
}
evenFirst = prev;
// Attach the reversed even linked
// list to odd linked list
odd.next = evenFirst;
return head;
}
// A utility function to print a linked list
static void printlist(Node node)
{
while (node != null)
{
Console.Write( node.data + " -> ");
node = node.next;
}
Console.WriteLine( "null" );
}
// Driver code
public static void Main(String []args)
{
Node head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(5);
head.next.next.next.next.next = newNode(6);
head = rearrangeEvenOdd(head);
printlist(head);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to Append odd position nodes
// in reverse at the end of even
// positioned nodes in a Linked List
// Linked List Node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// A utility function to create a new node
function newNode(key) {
var temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// Rearranges given linked list such that all even
// positioned nodes are before odd positioned
// in a reverse
function rearrangeEvenOdd(head) {
// Corner case
if (head == null)
return null;
// Initialize first nodes of even and
// odd lists
var odd = head;
var even = head.next;
// Remember the first node of even list so
// that we can connect the even list at the
// end of odd list.
var evenFirst = even;
while (true) {
// If there are no more nodes, then connect
// first node of even list to the last node
// of odd list
if (odd == null || even == null ||
(even.next) == null)
{
break;
}
// Connecting odd nodes
odd.next = even.next;
odd = even.next;
// If there are NO more even nodes after
// current odd.
if (odd.next == null) {
even.next = null;
break;
}
// Connecting evenevenFirs nodes
even.next = odd.next;
even = odd.next;
}
// Reversal of even linked list
var current = evenFirst;
var prev = null;
var front = null;
// Iterate in the complete linked list
while (current != null) {
front = current.next;
current.next = prev;
prev = current;
current = front;
}
evenFirst = prev;
// Attach the reversed even linked
// list to odd linked list
odd.next = evenFirst;
return head;
}
// A utility function to print a linked list
function printlist(node) {
while (node != null) {
document.write(node.data + " -> ");
node = node.next;
}
document.write("Null");
}
// Driver code
var head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(5);
head.next.next.next.next.next = newNode(6);
head = rearrangeEvenOdd(head);
printlist(head);
// This code is contributed by todaysgaurav
</script>
Producción:
1 -> 3 -> 5 -> 6 -> 4 -> 2 -> NULL
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional para la string.