Dada una lista enlazada de enteros, escriba una función para modificar la lista enlazada de modo que todos los números pares aparezcan antes que todos los números impares en la lista enlazada modificada. Además, mantén el mismo orden de los números pares e impares.
Ejemplos:
Input: 17->15->8->12->10->5->4->1->7->6->NULL Output: 8->12->10->4->6->17->15->5->1->7->NULL Input: 8->12->10->5->4->1->6->NULL Output: 8->12->10->4->6->5->1->NULL // If all numbers are even then do not change the list Input: 8->12->10->NULL Output: 8->12->10->NULL // If all numbers are odd then do not change the list Input: 1->3->5->7->NULL Output: 1->3->5->7->NULL
Método 1:
la idea es obtener un puntero al último Node de la lista. Y luego recorra la lista comenzando desde el Node principal y mueva los Nodes con valores impares desde su posición actual hasta el final de la lista.
Gracias a Blunderboy por sugerir este método.
Algoritmo:
- Obtener puntero al último Node.
- Mueva todos los Nodes impares hasta el final.
- Considere todos los Nodes impares antes del primer Node par y muévalos al final.
- Cambie el puntero principal para que apunte al primer Node par.
- Considere todos los Nodes impares después del primer Node par y muévalos al final.
Java
// Java program to segregate even and
// odd nodes in a Linked List
class LinkedList
{
// Head of list
Node head;
// Linked list Node
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void segregateEvenOdd()
{
Node end = head;
Node prev = null;
Node curr = head;
// Get pointer to last Node
while (end.next != null)
end = end.next;
Node new_end = end;
// Consider all odd nodes before
// getting first eve node
while (curr.data % 2 !=0 &&
curr != end)
{
new_end.next = curr;
curr = curr.next;
new_end.next.next = null;
new_end = new_end.next;
}
// Do following steps only if
// there is an even node
if (curr.data % 2 == 0)
{
head = curr;
// Now curr points to first even node
while (curr != end)
{
if (curr.data % 2 == 0)
{
prev = curr;
curr = curr.next;
}
else
{
/* Break the link between prev
and curr*/
prev.next = curr.next;
// Make next of curr as null
curr.next = null;
// Move curr to end
new_end.next = curr;
// Make curr as new end of list
new_end = curr;
// Update curr pointer
curr = prev.next;
}
}
}
/* We have to set prev before
executing rest of this code */
else prev = curr;
if (new_end != end &&
end.data %2 != 0)
{
prev.next = end.next;
end.next = null;
new_end.next = end;
}
}
/* Given a reference (pointer to pointer)
to the head of a list and an int, push
a new node on the front of the list. */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
// 3. Make next of new Node as head
new_node.next = head;
// 4. Move the head to point to
// new Node
head = new_node;
}
// Utility function to print
// a linked list
void printList()
{
Node temp = head;
while(temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// Driver code
public static void main(String args[])
{
LinkedList llist = new LinkedList();
llist.push(11);
llist.push(10);
llist.push(8);
llist.push(6);
llist.push(4);
llist.push(2);
llist.push(0);
System.out.println(
"Original Linked List");
llist.printList();
llist.segregateEvenOdd();
System.out.println(
"Modified Linked List");
llist.printList();
}
}
// This code is contributed by Rajat Mishra
Producción:
Original Linked list 0 2 4 6 8 10 11 Modified Linked list 0 2 4 6 8 10 11
Complejidad temporal: O(n)
Método 2:
la idea es dividir la lista enlazada en dos: una que contenga todos los Nodes pares y otra que contenga todos los Nodes impares. Y finalmente, adjunte la lista vinculada de Nodes impares después de la lista vinculada de Nodes pares.
Para dividir la Lista vinculada, recorra la Lista vinculada original y mueva todos los Nodes impares a una Lista vinculada separada de todos los Nodes impares. Al final del ciclo, la lista original tendrá todos los Nodes pares y la lista de Nodes impares tendrá todos los Nodes impares. Para mantener el mismo orden de todos los Nodes, debemos insertar todos los Nodes impares al final de la lista de Nodes impares. Y para hacerlo en tiempo constante, debemos realizar un seguimiento del último puntero en la lista de Nodes impares.
Java
// Java program to segregate even and
// odd nodes in a Linked List
import java.io.*;
class LinkedList
{
// Head of list
Node head;
// Linked list Node
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
public void segregateEvenOdd()
{
Node evenStart = null;
Node evenEnd = null;
Node oddStart = null;
Node oddEnd = null;
Node currentNode = head;
while(currentNode != null)
{
int element = currentNode.data;
if(element % 2 == 0)
{
if(evenStart == null)
{
evenStart = currentNode;
evenEnd = evenStart;
}
else
{
evenEnd.next = currentNode;
evenEnd = evenEnd.next;
}
}
else
{
if(oddStart == null)
{
oddStart = currentNode;
oddEnd = oddStart;
}
else
{
oddEnd.next = currentNode;
oddEnd = oddEnd.next;
}
}
// Move head pointer one step
// in forward direction
currentNode = currentNode.next;
}
if(oddStart == null ||
evenStart == null)
{
return;
}
evenEnd.next = oddStart;
oddEnd.next = null;
head=evenStart;
}
/* Given a reference (pointer to pointer)
to the head of a list and an int, push
a new node on the front of the list. */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
// 3. Make next of new Node as head
new_node.next = head;
// 4. Move the head to point to new Node
head = new_node;
}
// Utility function to print
// a linked list
void printList()
{
Node temp = head;
while(temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// Driver code
public static void main(String args[])
{
LinkedList llist = new LinkedList();
llist.push(11);
llist.push(10);
llist.push(9);
llist.push(6);
llist.push(4);
llist.push(1);
llist.push(0);
System.out.println(
"Original Linked List");
llist.printList();
llist.segregateEvenOdd();
System.out.println(
"Modified Linked List");
llist.printList();
}
}
Producción:
Original Linked List 0 1 4 6 9 10 11 Modified Linked List 0 4 6 10 1 9 11
Complejidad de tiempo: O(n)
Consulte el artículo completo sobre Segregación de Nodes pares e impares en una lista enlazada 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