Reorganice una lista enlazada de tal manera que todos los Nodes de posiciones impares estén juntos y todos los Nodes de posiciones pares estén juntos.
Ejemplos:
Input: 1->2->3->4 Output: 1->3->2->4 Input: 10->22->30->43->56->70 Output: 10->30->56->22->43->70
Lo importante en esta pregunta es asegurarse de que todos los casos a continuación se manejen
C++
// C++ program to rearrange a linked list in such a
// way that all odd positioned node are stored before
// all even positioned nodes
#include<bits/stdc++.h>
using namespace std;
// Linked List Node
class Node
{
public:
int data;
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.
// Returns new head of linked List.
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))
{
odd->next = evenFirst;
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;
odd->next = evenFirst;
break;
}
// Connecting even nodes
even->next = odd->next;
even = odd->next;
}
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);
cout << "Given Linked List\n";
printlist(head);
head = rearrangeEvenOdd(head);
cout << "Modified Linked List\n";
printlist(head);
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program to rearrange a linked list in such a
// way that all odd positioned node are stored before
// all even positioned nodes
#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.
// Returns new head of linked List.
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))
{
odd->next = evenFirst;
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;
odd->next = evenFirst;
break;
}
// Connecting even nodes
even->next = odd->next;
even = odd->next;
}
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);
cout << "Given Linked List\n";
printlist(head);
head = rearrangeEvenOdd(head);
cout << "\nModified Linked List\n";
printlist(head);
return 0;
}
Java
// Java program to rearrange a linked list
// in such a way that all odd positioned
// node are stored before all even positioned nodes
class GfG
{
// 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.
// Returns new head of linked List.
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 (1 == 1)
{
// 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)
{
odd.next = evenFirst;
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;
odd.next = evenFirst;
break;
}
// Connecting even nodes
even.next = odd.next;
even = odd.next;
}
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);
System.out.println("Given Linked List");
printlist(head);
head = rearrangeEvenOdd(head);
System.out.println("Modified Linked List");
printlist(head);
}
}
// This code is contributed by Prerna saini
Python3
# Python3 program to rearrange a linked list
# in such a way that all odd positioned
# node are stored before all even positioned nodes
# Linked List Node
class Node:
def __init__(self, d):
self.data = d
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# A utility function to create
# a new node
def newNode(self, key):
temp = Node(key)
self.next = None
return temp
# Rearranges given linked list
# such that all even positioned
# nodes are before odd positioned.
# Returns new head of linked List.
def rearrangeEvenOdd(self, head):
# Corner case
if (self.head == None):
return None
# Initialize first nodes of
# even and odd lists
odd = self.head
even = self.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 (1 == 1):
# 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):
odd.next = evenFirst
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
odd.next = evenFirst
break
# Connecting even nodes
even.next = odd.next
even = odd.next
return head
# A utility function to print a linked list
def printlist(self, node):
while (node != None):
print(node.data, end = "")
print("->", end = "")
node = node.next
print ("NULL")
# Function to insert a new node
# at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Driver code
ll = LinkedList()
ll.push(5)
ll.push(4)
ll.push(3)
ll.push(2)
ll.push(1)
print ("Given Linked List")
ll.printlist(ll.head)
start = ll.rearrangeEvenOdd(ll.head)
print ("\nModified Linked List")
ll.printlist(start)
# This code is contributed by Prerna Saini
C#
// C# program to rearrange a linked list
// in such a way that all odd positioned
// node are stored before all even positioned nodes
using System;
class GfG
{
// Linked List Node
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.
// Returns new head of linked List.
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 (1 == 1)
{
// 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)
{
odd.next = evenFirst;
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;
odd.next = evenFirst;
break;
}
// Connecting even nodes
even.next = odd.next;
even = odd.next;
}
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()
{
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);
Console.WriteLine("Given Linked List");
printlist(head);
head = rearrangeEvenOdd(head);
Console.WriteLine("Modified Linked List");
printlist(head);
}
}
/* This code is contributed PrinciRaj1992 */
Javascript
<script>
// Javascript program to rearrange a linked list
// in such a way that all odd positioned
// node are stored before all even positioned nodes
// 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.
// Returns new head of linked List.
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 (1 == 1) {
// 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)
{
odd.next = evenFirst;
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;
odd.next = evenFirst;
break;
}
// Connecting even nodes
even.next = odd.next;
even = odd.next;
}
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<br/>");
}
// 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);
document.write("Given Linked List<br/>");
printlist(head);
head = rearrangeEvenOdd(head);
document.write("Modified Linked List<br/>");
printlist(head);
// This code contributed by gauravrajput1
</script>
C++
// C++ Code in Odd -> Even Index Position
#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;
}
void rearrangeEvenOdd(Node *head)
{
if(head==NULL || head->next == NULL){
// 0 or 1 node
return;
}
Node* temp = head;
Node* oddStart = NULL; //ODD INDEX
Node* oddEnd = NULL;
Node* evenStart = NULL; //EVEN INDEX
Node* evenEnd = NULL;
int i = 1;
while(temp != NULL){
if(i%2 ==0){
//even
if(evenStart == NULL){
evenStart = temp;
}
else{
evenEnd->next = temp;
}
evenEnd = temp;
}
else{
//odd
if(oddStart == NULL){
oddStart = temp;
}
else{
oddEnd->next = temp;
}
oddEnd = temp;
}
temp = temp->next;
i++;
}
//now join the odd end with even start
oddEnd->next = evenStart;
//even end is new end so put NULL
evenEnd->next = NULL;
head = oddStart; //new head
}
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);
cout << "Given Linked List\n";
printlist(head);
rearrangeEvenOdd(head);
cout << "\nModified Linked List\n";
printlist(head);
return 0;
}
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