Reorganizar la lista enlazada para hacer XOR de Nodes a la misma distancia desde el inicio y el final

Dada una lista enlazada que contiene N Nodes de números binarios , la tarea es verificar si es posible reorganizar la lista enlazada de tal manera que el valor de XOR entre el elemento en el i- ésimo Node y el N+1-ésimo Node sea el mismo para todos los 1 ≤ i ≤ N. Imprimir Sí , si la Lista enlazada se puede reorganizar , o imprimir No.

Ejemplos:

Entrada: LL = 0 -> 0 -> 1
Salida: Sí
Explicación: 001 se puede reorganizar para formar 010, lo que significa que 0 ⊕ 0 = 0 y 1 ⊕ 1 =0 son iguales. Entonces la salida es 1.

Entrada: 0001 (0->0->0->1)
Salida: No
Explicación: 0001 no se puede reorganizar. Entonces la salida es 0.

Enfoque: La idea se basa en el recorrido de lista enlazada , basado en las siguientes observaciones: 

Caso 1: si el tamaño de la lista enlazada es impar, siempre es posible. Así que devuelve directamente Yes . 
Por ejemplo:

• 00001 se puede reorganizar como 00100
• 00011 se puede reorganizar como 10001
• 00111 se puede reorganizar como 10101
• 01111 se puede reorganizar como 11011

Caso 2: si el tamaño de la lista enlazada es par, cuente el número de 1 presente en la lista enlazada. Si el número de 1 presentes en la lista enlazada es igual a la mitad del tamaño de la lista enlazada, devuelva Yes , porque siempre será posible la reorganización.
Por ejemplo: 

• 0011  
  número de 1 = la mitad del tamaño de la lista enlazada, 
  por lo que se puede reorganizar como 1001
• 001101  
  número de 1 = la mitad del tamaño de la lista enlazada, 
  por lo que se puede reorganizar como 010101

Caso 3: si el número de 1 presentes en nuestra lista enlazada es par, también siempre es posible. Así que devuelve directamente Yes .
Por ejemplo: 

• 000011 se puede reorganizar como 100001 o 001100
• 011 se puede reorganizar como 101

Caso 4: si todas las condiciones anteriores son falsas, devuelva No .
Por ejemplo: 

• 011111 no se puede reorganizar
• 000001 no se puede reorganizar

Siga los pasos a continuación para implementar el enfoque anterior:

• Calcular el tamaño de la lista enlazada.
• Si el tamaño es impar, devuelva 1 porque siempre es posible reorganizar la lista vinculada como se explicó anteriormente.
• Si el tamaño es par, cuente el número de Nodes que consisten en valor 1.
• Si el recuento del número de Nodes consta de valor 1 es la mitad del tamaño de la lista vinculada, entonces devuelve 1.
• Si el tamaño es par y el recuento del número de Nodes que consisten en valor 1 es par, entonces devuelve 1.
• Si todas las condiciones anteriores no se ejecutan, devuelva 0.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach:
#include <iostream>
using namespace std;
 
// Node Class
class Node {
public:
    int data;
    Node* next;
};
 
// Function to append the node
void append(Node** head_ref, int new_data)
{
    Node* new_node = new Node();
    Node* last = *head_ref;
    new_node->data = new_data;
    new_node->next = NULL;
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
    return;
}
 
// Count the size of linked list
int CountSize(Node* head)
{
    Node* temp = head;
    int count = 0;
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}
 
// Bool function to check
// is it possible to make
// such linked list
bool isPossible(Node* head)
{
 
    // count size of linked list
    int n = CountSize(head);
 
    // if n is odd
    if (n % 2 != 0) {
        return 1;
    }
 
    else {
        int o = 0;
        Node* temp = head;
 
        while (temp != NULL) {
            if (temp->data == 1) {
                o++;
            }
            temp = temp->next;
        }
 
        if (o == (n / 2)) {
            return 1;
        }
        else if (o % 2 == 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}
 
// Driver Code
int main()
{
    Node* head = NULL;
    append(&head, 0);
    append(&head, 0);
    append(&head, 1);
    append(&head, 1);
 
    cout << (isPossible(head) == 1
                 ? "Yes"
                 : "No")
         << endl;
}

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
  // Structure of a binary tree node
  public static class Node {
    int data;
    Node next;
 
    Node(int data)
    {
      this.data = data;
      this.next = null;
 
    }
  }
 
  // Count the size of linked list
  static int CountSize(Node head) {
    Node temp = head;
    int count = 0;
    while (temp != null) {
      count++;
      temp = temp.next;
    }
    return count;
  }
 
  // Bool function to check
  // is it possible to make
  // such linked list
  static int isPossible(Node head) {
 
    // count size of linked list
    int n = CountSize(head);
 
    // if n is odd
    if (n % 2 != 0) {
      return 1;
    }
 
    else {
      int o = 0;
      Node temp = head;
 
      while (temp != null) {
        if (temp.data == 1) {
          o++;
        }
        temp = temp.next;
      }
 
      if (o == Math.floor(n / 2)) {
        return 1;
      }
      else if (o % 2 == 0) {
        return 1;
      }
      else {
        return 0;
      }
    }
  }
 
 
  // Driver Code
  public static void main(String[] args)
  {
    Node head = new Node(1);
    head.next = new Node(1);
    head.next.next = new Node(0);
    head.next.next.next = new Node(0);
    System.out.println((isPossible(head) == 1
                        ? "Yes"
                        : "No"));
  }
}
 
// This code is contributed by jana_sayantan.

# Python code for the above approach
 
# Node Class
class Node:
    def __init__(self,d):
            self.data = d
            self.next = None
             
# Count the size of linked list
def CountSize(head):
    temp = head
    count = 0
    while (temp != None):
        count += 1
        temp = temp.next
     
    return count
 
# Bool function to check
# is it possible to make
# such linked list
def isPossible(head):
 
    # count size of linked list
    n = CountSize(head)
 
    # if n is odd
    if (n % 2 != 0):
        return 1
 
    else:
        o = 0
        temp = head
 
        while (temp != None):
            if (temp.data == 1):
                o += 1
             
            temp = temp.next
         
 
        if (o == (n // 2)):
            return 1
         
        elif (o % 2 == 0):
            return 1
 
        else:
            return 0
 
# Driver Code
head = Node(1)
head.next = Node(1)
head.next.next = Node(0)
head.next.next.next = Node(0)
print("Yes" if(isPossible(head) == 1) else "No")
 
# This code is contributed by shinjanpatra

// C# program to implement above approach
using System;
 
public class Node {
     public int data;
     public Node next;
     public Node(int d)
     {
        data = d;
        next = null;
     } // Constructor
}
 
public class LinkedList{
  public Node head;
   
      // Count the size of linked list
  public int CountSize()
  {
      Node temp = head;
      int count = 0;
      while (temp != null) {
          count++;
          temp = temp.next;
      }
      return count;
  }
   
  public Node append(Node node,int val)
  {
    Node new_node = new Node(val);
    node.next = new_node;
    return new_node;
  }
}
 
public class GFG
{
  public static bool isPossible(LinkedList LL)
  {
 
      // count size of linked list
      int n = LL.CountSize();
 
      // if n is odd
      if (n % 2 != 0) {
          return true;
      }
      else
      {
          int o = 0;
          Node temp = LL.head;
 
          while (temp != null) {
              if (temp.data == 1) {
                  o++;
              }
              temp = temp.next;
          }
 
          if (o == (n / 2)) {
              return true;
          }
          else if (o % 2 == 0) {
              return true;
          }
          else {
              return false;
          }
      }
  }
   
  // Driver Code
  public static void Main()
  {
    LinkedList llist = new LinkedList();
   
    llist.head = new Node(0);
    Node cur = llist.head;
    cur = llist.append(cur, 0);
    cur = llist.append(cur, 1);
    cur = llist.append(cur, 1);
     
    if(isPossible(llist))
    {
        Console.Write("Yes\n");
    }
    else
    {
          Console.Write("No\n");
    }
  }
}
 
// This code is contributed by subhamgoyal2014.

<script>
        // JavaScript code for the above approach
 
        // Node Class
        class Node {
            constructor(d) {
                this.data = d;
                this.next = null;
            }
        };
 
        // Count the size of linked list
        function CountSize(head) {
            let temp = head;
            let count = 0;
            while (temp != null) {
                count++;
                temp = temp.next;
            }
            return count;
        }
 
        // Bool function to check
        // is it possible to make
        // such linked list
        function isPossible(head) {
 
            // count size of linked list
            let n = CountSize(head);
 
            // if n is odd
            if (n % 2 != 0) {
                return 1;
            }
 
            else {
                let o = 0;
                let temp = head;
 
                while (temp != null) {
                    if (temp.data == 1) {
                        o++;
                    }
                    temp = temp.next;
                }
 
                if (o == Math.floor(n / 2)) {
                    return 1;
                }
                else if (o % 2 == 0) {
                    return 1;
                }
                else {
                    return 0;
                }
            }
        }
 
        // Driver Code
        let head = new Node(1);
        head.next = new Node(1);
        head.next.next = new Node(0)
        head.next.next.next = new Node(0)
        document.write((isPossible(head) == 1
            ? "Yes"
            : "No")
            + '<br>')
 
     // This code is contributed by Potta Lokesh
    </script>

Yes

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)