Divida la lista enlazada dada en dos listas de proporción de tamaño p:q

Dada una lista enlazada y dos enteros p y q , la tarea es dividir la lista enlazada en la proporción p:q, es decir, la primera lista contiene los primeros p Nodes de la lista original y la segunda lista contiene el resto de los q Nodes. Si la lista original no se puede dividir en la proporción dada, imprima -1 .
Ejemplos: 
 

Entrada: 1 -> 3 -> 5 -> 6 -> 7 -> 2 -> NULO 
p = 2, q = 4 
Salida: 
1 3 
5 6 7 2
Entrada: 1 -> 2 -> 4 -> 9 -> NULO 
p = 3, q ​​= 2 
Salida: -1 
 

Enfoque: Primero encuentre la longitud de la lista enlazada. Si la suma de la relación total excede la longitud real, entonces no es posible dividir la lista, así que imprima -1 . Si es posible dividir la lista, simplemente recorra la lista hasta la longitud p y divídala en la proporción p:q . El siguiente Node será el encabezado de la segunda lista y luego imprimirá ambas listas.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
struct Node
{
    int data;
    Node *next;
 
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
 
void printList(Node *);
 
// Function to split the given linked list
// into ratio of p and q
void splitAndPrint(Node *head, int p, int q)
{
  int n = 0;
  Node *temp;
  temp = head;
 
  // Find the length of the list
  while (temp != NULL)
  {
    n += 1;
    temp = temp->next;
  }
 
  // If ration exceeds the actual length
  if (p + q > n)
  {
    cout << "-1" << endl;
    return;
  }
  temp = head;
  while (p > 1)
  {
    temp = temp->next;
    p -= 1;
  }
 
  // second head node after splitting
  Node *head2 = temp->next;
  temp->next = NULL;
 
  // Print first linked list
  printList(head);
  cout << endl;
 
  // Print second linked list
  printList(head2);
}
 
// Function to print the nodes
// of the linked list
void printList(Node* head)
{
  if (head == NULL)
    return;
  cout << head->data << " ";
  printList(head->next);
}
 
// Driver code
int main()
{
  Node* head = new Node(1);
  head->next = new Node(3);
  head->next->next = new Node(5);
  head->next->next->next = new Node(6);
  head->next->next->next->next = new Node(7);
  head->next->next->next->next->next = new Node(2);
 
  int p = 2, q = 4;
  splitAndPrint(head, p, q);
}
 
// This code is contributed by rutvik_56.

// Java implementation of the approach
class GFG
{
     
// Node
static class Node
{
    int data;
    Node next;
    Node(int data)
    {
        this.data = data;
    }
}
 
// Function to split the given linked list
// into ratio of p and q
static void splitAndPrint(Node head,int p,int q)
{
    int n = 0;
    Node temp;
    temp = head;
     
    // Find the length of the list
    while(temp!=null)
    {
        n += 1;
        temp = temp.next;
    }
     
    // If ration exceeds the actual length
    if (p + q > n)
    {
        System.out.println("-1");
        return;
    }
    temp = head;
    while(p > 1)
    {
        temp = temp.next;
        p-= 1;
    }
     
    // second head node after splitting
    Node head2 = temp.next;
    temp.next = null;
     
    // Print first linked list
    printList(head);
    System.out.println();
     
    // Print second linked list
    printList(head2);
}
 
// Function to print the nodes
// of the linked list
static void printList(Node head)
{
    if( head == null)
        return;
    System.out.print(head.data+" , ");
    printList(head.next);
}
 
// Driver code
public static void main(String args[])
{
    Node head = new Node(1);
    head.next = new Node(3);
    head.next.next = new Node(5);
    head.next.next.next = new Node(6);
    head.next.next.next.next = new Node(7);
    head.next.next.next.next.next = new Node(2);
     
    int p =2,q= 4;
    splitAndPrint(head, p, q);
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
 
# Linked List node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# Function to split the given linked list
# into ratio of p and q
def splitAndPrint(head, p, q):
    n, temp = 0, head
     
    # Find the length of the list
    while(temp):
        n += 1
        temp = temp.next
     
    # If ration exceeds the actual length
    if p + q>n:
        print("-1")
        return
 
    temp = head
    while(p>1):
        temp = temp.next
        p-= 1
     
    # second head node after splitting
    head2 = temp.next
    temp.next = None
     
    # Print first linked list
    printList(head)
    print()
     
    # Print second linked list
    printList(head2)
 
# Function to print the nodes
# of the linked list
def printList(head):
    if not head:
        return
    print("{} ".format(head.data), end ="")
    printList(head.next)
 
# Driver code
head = Node(1)
head.next = Node(3)
head.next.next = Node(5)
head.next.next.next = Node(6)
head.next.next.next.next = Node(7)
head.next.next.next.next.next = Node(2)
 
p, q = 2, 4
splitAndPrint(head, p, q)

// C# implementation of the approach
using System;
 
class GFG
{
     
public class Node
{
    public int data;
    public Node next;
    public Node(int data)
    {
        this.data = data;
    }
}
 
// Function to split the given linked list
// into ratio of p and q
static void splitAndPrint(Node head,int p,int q)
{
    int n = 0;
    Node temp;
    temp = head;
     
    // Find the length of the list
    while(temp != null)
    {
        n += 1;
        temp = temp.next;
    }
     
    // If ration exceeds the actual length
    if (p + q > n)
    {
        Console.WriteLine("-1");
        return;
    }
    temp = head;
    while(p > 1)
    {
        temp = temp.next;
        p-= 1;
    }
     
    // second head node after splitting
    Node head2 = temp.next;
    temp.next = null;
     
    // Print first linked list
    printList(head);
    Console.WriteLine();
     
    // Print second linked list
    printList(head2);
}
 
// Function to print the nodes
// of the linked list
static void printList(Node head)
{
    if( head == null)
        return;
    Console.Write(head.data+" ");
    printList(head.next);
}
 
// Driver code
public static void Main(String []args)
{
    Node head = new Node(1);
    head.next = new Node(3);
    head.next.next = new Node(5);
    head.next.next.next = new Node(6);
    head.next.next.next.next = new Node(7);
    head.next.next.next.next.next = new Node(2);
     
    int p = 2, q = 4;
    splitAndPrint(head, p, q);
}
}
 
/* This code contributed by PrinciRaj1992 */

<script>
 
// Javascript implementation of the approach
 
// Node
class Node
{
        constructor(data)
        {
            this.data = data;
         }
}
 
// Function to split the given linked list
// into ratio of p and q
function splitAndPrint( head, p, q)
{
    var n = 0;
    var temp;
    temp = head;
     
    // Find the length of the list
    while(temp!=null)
    {
        n += 1;
        temp = temp.next;
    }
     
    // If ration exceeds the actual length
    if (p + q > n)
    {
        document.write("-1");
        return;
    }
    temp = head;
    while(p > 1)
    {
        temp = temp.next;
        p-= 1;
    }
     
    // second head node after splitting
    var head2 = temp.next;
    temp.next = null;
     
    // Print first linked list
    printList(head);
    document.write("</br>");
     
    // Print second linked list
    printList(head2);
}
 
// Function to print the nodes
// of the linked list
function printList(head)
{
    if( head == null)
        return;
    document.write(head.data + "  ");
    printList(head.next);
}
 
    // Driver Code
    let head = new Node(1);
    head.next = new Node(3);
    head.next.next = new Node(5);
    head.next.next.next = new Node(6);
    head.next.next.next.next = new Node(7);
    head.next.next.next.next.next = new Node(2);
     
    let p = 2, q = 4;
    splitAndPrint(head, p, q);
 
// This code is contributed by jana_sayantan.
</script>

1 3 
5 6 7 2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)