Dada una lista unida L 0 -> L 1 -> … -> L n-1 -> L n . Reorganice los Nodes en la lista para que la nueva lista formada sea: L 0 -> L n -> L 1 -> L n-1 -> L 2 -> L n-2 …
Debe hacer esto en su lugar sin alterando los valores de los Nodes.
Ejemplos:
Input: 1 -> 2 -> 3 -> 4 Output: 1 -> 4 -> 2 -> 3 Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 1 -> 5 -> 2 -> 4 -> 3
Solución simple:
1) Initialize current node as head.
2) While next of current node is not null, do following
a) Find the last node, remove it from the end and insert it as next
of the current node.
b) Move current to next to next of current
La complejidad temporal de la solución simple anterior es O(n 2 ) donde n es el número de Nodes en la lista enlazada.
Mejor solución:
1) Copie el contenido de la lista vinculada dada a un vector.
2) Reorganizar el vector dado intercambiando Nodes de ambos extremos.
3) Copie el vector modificado nuevamente a la lista enlazada.
Implementación de este enfoque: https://ide.geeksforgeeks.org/1eGSEy
Gracias a Arushi Dhamija por sugerir este enfoque.
Solución eficiente:
1) Find the middle point using tortoise and hare method. 2) Split the linked list into two halves using found middle point in step 1. 3) Reverse the second half. 4) Do alternate merge of first and second halves.
La complejidad temporal de esta solución es O(n).
A continuación se muestra la implementación de este método.
Java
// Java program to rearrange linked list
// in place
// Linked List Class
class LinkedList
{
// head of the list
static Node head;
// Node Class
static class Node
{
int data;
Node next;
// Constructor to create
// a new node
Node(int d)
{
data = d;
next = null;
}
}
void printlist(Node node)
{
if (node == null)
{
return;
}
while (node != null)
{
System.out.print(node.data +
" -> ");
node = node.next;
}
}
Node reverselist(Node node)
{
Node prev = null,
curr = node, next;
while (curr != null)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
node = prev;
return node;
}
void rearrange(Node node)
{
// 1) Find the middle point using
// tortoise and hare method
Node slow = node, fast = slow.next;
while (fast != null &&
fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
// 2) Split the linked list in
// two halves
// node1, head of first half-
// 1 -> 2 -> 3
// node2, head of second half-
// 4 -> 5
Node node1 = node;
Node node2 = slow.next;
slow.next = null;
// 3) Reverse the second half,
// i.e., 5 -> 4
node2 = reverselist(node2);
// 4) Merge alternate nodes
// Assign dummy Node
node = new Node(0);
// curr is the pointer to this
// dummy Node, which will be
// used to form the new list
Node curr = node;
while (node1 != null ||
node2 != null)
{
// First add the element
// from first list
if (node1 != null)
{
curr.next = node1;
curr = curr.next;
node1 = node1.next;
}
// Then add the element from
// second list
if (node2 != null)
{
curr.next = node2;
curr = curr.next;
node2 = node2.next;
}
}
// Assign the head of the new
// list to head pointer
node = node.next;
}
// Driver code
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(1);
list.head.next = new Node(2);
list.head.next.next =
new Node(3);
list.head.next.next.next =
new Node(4);
list.head.next.next.next.next =
new Node(5);
// Print original list
list.printlist(head);
// Rearrange list as per ques
list.rearrange(head);
System.out.println("");
// Print modified list
list.printlist(head);
}
}
// This code is contributed by Mayank Jaiswal
Producción:
1 -> 2 -> 3 -> 4 -> 5 1 -> 5 -> 2 -> 4 -> 3
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
Gracias a Gaurav Ahirwar por sugerir el enfoque anterior.
Otro enfoque:
1. Tome dos punteros prev y curr, que contienen las direcciones de head y head-> next.
2. Compare sus datos e intercambie.
Después de eso, se forma una nueva lista enlazada.
A continuación se muestra la implementación:
Java
// Java code to rearrange linked list
// in place
class Geeks
{
static class Node
{
int data;
Node next;
}
// Function for rearranging a
// linked list with high and
// low value.
static Node rearrange(Node head)
{
// Base case
if (head == null)
return null;
// Two pointer variable.
Node prev = head,
curr = head.next;
while (curr != null)
{
// Swap function for swapping
// data.
if (prev.data > curr.data)
{
int t = prev.data;
prev.data = curr.data;
curr.data = t;
}
// Swap function for swapping data.
if (curr.next != null &&
curr.next.data > curr.data)
{
int t = curr.next.data;
curr.next.data = curr.data;
curr.data = t;
}
prev = curr.next;
if (curr.next == null)
break;
curr = curr.next.next;
}
return head;
}
// Function to insert a Node in
// the linked list at the beginning.
static Node push(Node head, int k)
{
Node tem = new Node();
tem.data = k;
tem.next = head;
head = tem;
return head;
}
// Function to display Node of
// linked list.
static void display(Node head)
{
Node curr = head;
while (curr != null)
{
System.out.printf("%d ",
curr.data);
curr = curr.next;
}
}
// Driver code
public static void main(String args[])
{
Node head = null;
// Let create a linked list.
// 9 . 6 . 8 . 3 . 7
head = push(head, 7);
head = push(head, 3);
head = push(head, 8);
head = push(head, 6);
head = push(head, 9);
head = rearrange(head);
display(head);
}
}
// This code is contributed by Arnab Kundu
Producción:
6 9 3 8 7
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
Gracias a Aditya por sugerir este enfoque.
Otro enfoque: (usando la recursividad)
- Mantenga un puntero en el Node principal y vaya hasta el último Node usando recursividad
- Una vez que se alcanza el último Node, comience a intercambiar el último Node con el siguiente Node principal
- Mover el puntero de la cabeza al siguiente Node
- Repita esto hasta que la cabeza y el último Node se encuentren o queden adyacentes entre sí.
- Una vez que se cumplió la condición de parada, debemos descartar los Nodes de la izquierda para corregir el bucle creado en la lista al intercambiar Nodes.
Java
// Java implementation
import java.io.*;
// Java program to implement
// the above approach
// Creating the structure
// for node
class Node
{
int data;
Node next;
// Function to create newNode
// in a linkedlist
Node(int key)
{
data = key;
next = null;
}
}
class GFG
{
Node left = null;
// Function to print the list
void printlist(Node head)
{
while (head != null)
{
System.out.print(head.data +
" ");
if (head.next != null)
{
System.out.print("->");
}
head = head.next;
}
System.out.println();
}
// Function to rearrange
void rearrange(Node head)
{
if (head != null)
{
left = head;
reorderListUtil(left);
}
}
void reorderListUtil(Node right)
{
if (right == null)
{
return;
}
reorderListUtil(right.next);
// We set left = null, when we
// reach stop condition, so no
// processing required after that
if (left == null)
{
return;
}
// Stop condition: odd case :
// left = right, even
// case : left.next = right
if (left != right &&
left.next != right)
{
Node temp = left.next;
left.next = right;
right.next = temp;
left = temp;
}
else
{
// stop condition , set null
// to left nodes
if (left.next == right)
{
// even case
left.next.next = null;
left = null;
}
else
{
// odd case
left.next = null;
left = null;
}
}
}
// Drivers Code
public static void main(String[] args)
{
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next =
new Node(4);
head.next.next.next.next =
new Node(5);
GFG gfg = new GFG();
// Print original list
gfg.printlist(head);
// Modify the list
gfg.rearrange(head);
// Print modified list
gfg.printlist(head);
}
}
// This code is contributed by Vishal Singh
Producción:
1 ->2 ->3 ->4 ->5 1 ->5 ->2 ->4 ->3
Complejidad de tiempo: O(n), donde n representa la longitud de la lista enlazada dada.
Espacio auxiliar: O(n), para pila recursiva donde n representa la longitud de la lista enlazada dada.
Consulte el artículo completo sobre Reorganizar una lista vinculada dada en el lugar. ¡para 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