Reorganizar una lista enlazada de modo que todos los Nodes posicionados pares e impares estén juntos

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *