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.
C++
// C++ program to rearrange a linked list in-place
#include <bits/stdc++.h>
using namespace std;
// Linkedlist Node structure
struct Node {
int data;
struct Node* next;
};
// Function to create newNode in a linkedlist
Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// Function to reverse the linked list
void reverselist(Node** head)
{
// Initialize prev and current pointers
Node *prev = NULL, *curr = *head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
// Function to print the linked list
void printlist(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
if (head->next)
cout << "-> ";
head = head->next;
}
cout << endl;
}
// Function to rearrange a linked list
void rearrange(Node** head)
{
// 1) Find the middle point using tortoise and hare
// method
Node *slow = *head, *fast = slow->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// 2) Split the linked list in two halves
// head1, head of first half 1 -> 2
// head2, head of second half 3 -> 4
Node* head1 = *head;
Node* head2 = slow->next;
slow->next = NULL;
// 3) Reverse the second half, i.e., 4 -> 3
reverselist(&head2);
// 4) Merge alternate nodes
*head = newNode(0); // Assign dummy Node
// curr is the pointer to this dummy Node, which will
// be used to form the new list
Node* curr = *head;
while (head1 || head2) {
// First add the element from list
if (head1) {
curr->next = head1;
curr = curr->next;
head1 = head1->next;
}
// Then add the element from the second list
if (head2) {
curr->next = head2;
curr = curr->next;
head2 = head2->next;
}
}
// Assign the head of the new list to head pointer
*head = (*head)->next;
}
// Driver program
int main()
{
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);
printlist(head); // Print original list
rearrange(&head); // Modify the list
printlist(head); // Print modified list
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to rearrange a linked list in-place
#include <stdio.h>
#include <stdlib.h>
// Linkedlist Node structure
typedef struct Node {
int data;
struct Node* next;
} Node;
// Function to create newNode in a linkedlist
Node* newNode(int key)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = key;
temp->next = NULL;
return temp;
}
// Function to reverse the linked list
void reverselist(Node** head)
{
// Initialize prev and current pointers
Node *prev = NULL, *curr = *head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
// Function to print the linked list
void printlist(Node* head)
{
while (head != NULL) {
printf("%d ", head->data);
if (head->next)
printf("-> ");
head = head->next;
}
printf("\n");
}
// Function to rearrange a linked list
void rearrange(Node** head)
{
// 1) Find the middle point using tortoise and hare
// method
Node *slow = *head, *fast = slow->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// 2) Split the linked list in two halves
// head1, head of first half 1 -> 2
// head2, head of second half 3 -> 4
Node* head1 = *head;
Node* head2 = slow->next;
slow->next = NULL;
// 3) Reverse the second half, i.e., 4 -> 3
reverselist(&head2);
// 4) Merge alternate nodes
*head = newNode(0); // Assign dummy Node
// curr is the pointer to this dummy Node, which will
// be used to form the new list
Node* curr = *head;
while (head1 || head2) {
// First add the element from list
if (head1) {
curr->next = head1;
curr = curr->next;
head1 = head1->next;
}
// Then add the element from the second list
if (head2) {
curr->next = head2;
curr = curr->next;
head2 = head2->next;
}
}
// Assign the head of the new list to head pointer
*head = (*head)->next;
}
// Driver program
int main()
{
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);
printlist(head); // Print original list
rearrange(&head); // Modify the list
printlist(head); // Print modified list
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to rearrange link list in place
// Linked List Class
class LinkedList {
static Node head; // head of the list
/* 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
node = new Node(0); // Assign dummy Node
// 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;
}
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);
list.printlist(head); // print original list
list.rearrange(head); // rearrange list as per ques
System.out.println("");
list.printlist(head); // print modified list
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python program to rearrange link list in place # Node Class class Node: # Constructor to create a new node def __init__(self, d): self.data = d self.next = None def printlist(node): if(node == None): return while(node != None): print(node.data," -> ", end = "") node = node.next def reverselist(node): prev = None curr = node next=None while (curr != None): next = curr.next curr.next = prev prev = curr curr = next node = prev return node def rearrange(node): # 1) Find the middle point using tortoise and hare # method slow = node fast = slow.next while (fast != None and fast.next != None): 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 node1 = node node2 = slow.next slow.next = None # 3) Reverse the second half, i.e., 5 -> 4 node2 = reverselist(node2) # 4) Merge alternate nodes node = Node(0) #Assign dummy Node # curr is the pointer to this dummy Node, which # will be used to form the new list curr = node while (node1 != None or node2 != None): # First add the element from first list if (node1 != None): curr.next = node1 curr = curr.next node1 = node1.next # Then add the element from second list if(node2 != None): curr.next = node2 curr = curr.next node2 = node2.next # Assign the head of the new list to head pointer node = node.next head = None head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) printlist(head) #print original list rearrange(head) #rearrange list as per ques print() printlist(head) #print modified list # This code is contributed by ab2127
C#
// C# program to rearrange link list in place
using System;
// Linked List Class
public class LinkedList {
Node head; // head of the list
/* Node Class */
class Node {
public int data;
public Node next;
// Constructor to create a new node
public Node(int d)
{
data = d;
next = null;
}
}
void printlist(Node node)
{
if (node == null) {
return;
}
while (node != null) {
Console.Write(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
node = new Node(0); // Assign dummy Node
// 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);
list.printlist(list.head); // print original list
list.rearrange(
list.head); // rearrange list as per ques
Console.WriteLine("");
list.printlist(list.head); // print modified list
}
}
/* This code is contributed PrinciRaj1992 */
Javascript
<script>
// Javascript program to rearrange link list in place
// Linked List Class
var head; // head of the list
/* Node Class */
class Node {
// Constructor to create a new node
constructor(d) {
this.data = d;
this.next = null;
}
}
function printlist(node) {
if (node == null) {
return;
}
while (node != null) {
document.write(node.data + " -> ");
node = node.next;
}
}
function reverselist(node) {
var prev = null, curr = node, next;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
node = prev;
return node;
}
function rearrange(node) {
// 1) Find the middle point using tortoise and hare
// method
var 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
var node1 = node;
var node2 = slow.next;
slow.next = null;
// 3) Reverse the second half, i.e., 5 -> 4
node2 = reverselist(node2);
// 4) Merge alternate nodes
node = new Node(0); // Assign dummy Node
// curr is the pointer to this dummy Node, which
// will be used to form the new list
var 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;
}
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);
printlist(head); // print original list
rearrange(head); // rearrange list as per ques
document.write("<br/>");
printlist(head); // print modified list
// This code contributed by gauravrajput1
</script>
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:
C++
// C++ code to rearrange linked list in place
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node* next;
};
typedef struct node Node;
// function for rearranging a linked list with high and low
// value.
void rearrange(Node* head)
{
if (head == NULL) // Base case.
return;
// two pointer variable.
Node *prev = head, *curr = head->next;
while (curr) {
// swap function for swapping data.
if (prev->data > curr->data)
swap(prev->data, curr->data);
// swap function for swapping data.
if (curr->next && curr->next->data > curr->data)
swap(curr->next->data, curr->data);
prev = curr->next;
if (!curr->next)
break;
curr = curr->next->next;
}
}
// function to insert a node in the linked list at the
// beginning.
void push(Node** head, int k)
{
Node* tem = (Node*)malloc(sizeof(Node));
tem->data = k;
tem->next = *head;
*head = tem;
}
// function to display node of linked list.
void display(Node* head)
{
Node* curr = head;
while (curr != NULL) {
printf("%d ", curr->data);
curr = curr->next;
}
}
// driver code
int main()
{
Node* head = NULL;
// let create a linked list.
// 9 -> 6 -> 8 -> 3 -> 7
push(&head, 7);
push(&head, 3);
push(&head, 8);
push(&head, 6);
push(&head, 9);
rearrange(head);
display(head);
return 0;
}
C
// C code to rearrange linked list in place
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// function for rearranging a linked list with high and low
// value.
void rearrange(Node* head)
{
if (head == NULL) // Base case.
return;
// two pointer variable.
Node *prev = head, *curr = head->next;
while (curr) {
// swap function for swapping data.
if (prev->data > curr->data) {
int temp = prev->data;
prev->data = curr->data;
curr->data = temp;
}
// swap function for swapping data.
if (curr->next && curr->next->data > curr->data) {
int temp = curr->next->data;
curr->next->data = curr->data;
curr->data = temp;
}
prev = curr->next;
if (!curr->next)
break;
curr = curr->next->next;
}
}
// function to insert a node in the linked list at the
// beginning.
void push(Node** head, int k)
{
Node* tem = (Node*)malloc(sizeof(Node));
tem->data = k;
tem->next = *head;
*head = tem;
}
// function to display node of linked list.
void display(Node* head)
{
Node* curr = head;
while (curr != NULL) {
printf("%d ", curr->data);
curr = curr->next;
}
}
// driver code
int main()
{
Node* head = NULL;
// let create a linked list.
// 9 -> 6 -> 8 -> 3 -> 7
push(&head, 7);
push(&head, 3);
push(&head, 8);
push(&head, 6);
push(&head, 9);
rearrange(head);
display(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
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)
{
if (head == null) // Base case.
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
Python3
# Python3 code to rearrange linked list in place class Node: def __init__(self, x): self.data = x self.next = None # Function for rearranging a linked # list with high and low value def rearrange(head): # Base case if (head == None): return head # Two pointer variable prev, curr = head, head.next while (curr): # Swap function for swapping data if (prev.data > curr.data): prev.data, curr.data = curr.data, prev.data # Swap function for swapping data if (curr.next and curr.next.data > curr.data): curr.next.data, curr.data = curr.data, curr.next.data prev = curr.next if (not curr.next): break curr = curr.next.next return head # Function to insert a node in the # linked list at the beginning def push(head, k): tem = Node(k) tem.data = k tem.next = head head = tem return head # Function to display node of linked list def display(head): curr = head while (curr != None): print(curr.data, end=" ") curr = curr.next # Driver code if __name__ == '__main__': head = None # 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 mohit kumar 29
C#
// C# code to rearrange linked list in place
using System;
class GFG {
class Node {
public int data;
public 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) {
Console.Write(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 rutvik_56
Javascript
<script>
// Javascript code to rearrange linked list in place
class Node
{
constructor()
{
this.data;
this.next=null;
}
}
// function for rearranging a linked list
// with high and low value.
function rearrange(head)
{
if (head == null) // Base case.
return null;
// two pointer variable.
let prev = head, curr = head.next;
while (curr != null)
{
// swap function for swapping data.
if (prev.data > curr.data) {
let t = prev.data;
prev.data = curr.data;
curr.data = t;
}
// swap function for swapping data.
if (curr.next != null
&& curr.next.data > curr.data) {
let 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 display Node of linked list.
function display(head)
{
let curr = head;
while (curr != null) {
document.write(curr.data+" ");
curr = curr.next;
}
}
// function to insert a Node in
// the linked list at the beginning.
function push(head,k)
{
let tem = new Node();
tem.data = k;
tem.next = head;
head = tem;
return head;
}
// Driver code
let head = null;
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 unknown2108
</script>
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.
C++
// C++ implementation
#include <bits/stdc++.h>
using namespace std;
// Creating the structure for node
struct Node {
int data;
struct Node* next;
};
// Function to create newNode in a linkedlist
Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// Function to print the list
void printlist(Node* head)
{
while (head) {
cout << head->data;
if (head->next)
cout << "->";
head = head->next;
}
cout << endl;
}
// Function to rearrange
void rearrange(Node** head, Node* last)
{
if (!last)
return;
// Recursive call
rearrange(head, last->next);
// (*head)->next will be set to NULL after
// rearrangement. Need not do any operation further Just
// return here to come out of recursion
if (!(*head)->next)
return;
// Rearrange the list until both head and last meet or
// next to each other.
if ((*head) != last && (*head)->next != last) {
Node* tmp = (*head)->next;
(*head)->next = last;
last->next = tmp;
*head = tmp;
}
else {
if ((*head) != last)
*head = (*head)->next;
(*head)->next = NULL;
}
}
// Drivers Code
int main()
{
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);
// Print original list
printlist(head);
Node* tmp = head;
// Modify the list
rearrange(&tmp, head);
// Print modified list
printlist(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C implementation
#include <stdio.h>
#include <stdlib.h>
// Creating the structure for node
typedef struct Node {
int data;
struct Node* next;
}Node;
// Function to create newNode in a linkedlist
Node* newNode(int key)
{
Node* temp = malloc(sizeof(Node));
temp->data = key;
temp->next = NULL;
return temp;
}
// Function to print the list
void printlist(Node* head)
{
while (head) {
printf("%d ", head->data);
if (head->next)
printf("->");
head = head->next;
}
printf("\n");
}
// Function to rearrange
void rearrange(Node** head, Node* last)
{
if (!last)
return;
// Recursive call
rearrange(head, last->next);
// (*head)->next will be set to NULL
// after rearrangement.
// Need not do any operation further
// Just return here to come out of recursion
if (!(*head)->next)
return;
// Rearrange the list until both head
// and last meet or next to each other.
if ((*head) != last && (*head)->next != last) {
Node* tmp = (*head)->next;
(*head)->next = last;
last->next = tmp;
*head = tmp;
}
else {
if ((*head) != last)
*head = (*head)->next;
(*head)->next = NULL;
}
}
// Drivers Code
int main()
{
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);
// Print original list
printlist(head);
Node* tmp = head;
// Modify the list
rearrange(&tmp, head);
// Print modified list
printlist(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java implementation
import java.io.*;
// 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) {
left.next.next = null; // even case
left = null;
}
else {
left.next = null; // odd case
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
Python3
# Python3 implementation
class Node:
def __init__(self, key):
self.data = key
self.next = None
left = None
# Function to print the list
def printlist(head):
while (head != None):
print(head.data, end = " ")
if (head.next != None):
print("->", end = "")
head = head.next
print()
# Function to rearrange
def rearrange(head):
global left
if (head != None):
left = head
reorderListUtil(left)
def reorderListUtil(right):
global left
if (right == None):
return
reorderListUtil(right.next)
# We set left = null, when we reach stop
# condition, so no processing required
# after that
if (left == None):
return
# Stop condition: odd case : left = right, even
# case : left.next = right
if (left != right and left.next != right):
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 = None
left = None
else:
# Odd case
left.next = None
left = None
# Driver code
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
# Print original list
printlist(head)
# Modify the list
rearrange(head)
# Print modified list
printlist(head)
# This code is contributed by patel2127
C#
// C# implementation
using System;
// Creating the structure for node
public class Node
{
public int data;
public Node next;
// Function to create newNode
// in a linkedlist
public Node(int key)
{
data = key;
next = null;
}
}
class GFG{
Node left = null;
// Function to print the list
void printlist(Node head)
{
while (head != null)
{
Console.Write(head.data + " ");
if (head.next != null)
{
Console.Write("->");
}
head = head.next;
}
Console.WriteLine();
}
// 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;
}
}
}
// Driver Code
static public void Main()
{
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 rag2127
Javascript
<script>
// javascript implementation// Creating the structure for node
class Node {
// Function to create newNode in a linkedlist
constructor(val) {
this.data = val;
this.next = null;
}
}
var left = null;
// Function to print the list
function printlist(head) {
while (head != null) {
document.write(head.data + " ");
if (head.next != null) {
document.write("->");
}
head = head.next;
}
document.write("<br/>");
}
// Function to rearrange
function rearrange(head) {
if (head != null) {
left = head;
reorderListUtil(left);
}
}
function reorderListUtil(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) {
var temp = left.next;
left.next = right;
right.next = temp;
left = temp;
} else { // stop condition , set null to left nodes
if (left.next == right) {
left.next.next = null; // even case
left = null;
} else {
left.next = null; // odd case
left = null;
}
}
}
// Drivers Code
var 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);
// Print original list
printlist(head);
// Modify the list
rearrange(head);
// Print modified list
printlist(head);
// This code contributed by aashish1995
</script>
Producción:
1 ->2 ->3 ->4 ->5 1 ->5 ->2 ->4 ->3
Complejidad temporal : O(N) donde N no es ningún Node de la lista enlazada
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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