Разделите данный связанный список на два списка с соотношением размеров p: q.
Учитывая связанный список и два целых числа p и q , задача состоит в том, чтобы разделить связанный список в соотношении p: q, т.е. первый список содержит первые p узлов из исходного списка, а второй список содержит оставшиеся q узлов. Если исходный список нельзя разделить с заданным соотношением, выведите -1 .
Примеры:
Input: 1 -> 3 -> 5 -> 6 -> 7 -> 2 -> NULL
p = 2, q = 4
Output:
1 3
5 6 7 2
Input: 1 -> 2 -> 4 -> 9 -> NULL
p = 3, q = 2
Output: -1
Approach: First find the length of the linked list. If the total ratio sum exceeds the actual length then dividing the list is not possible so print -1. If it is possible to divide the list then simply traverse the list up to length p and break it into the ratio p:q. Next node will be the head of the second list then print both the lists.
Below is the implementation of the above approach:
C++
// 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
// 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 |
Python
# 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#
// 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 */ |
1 3 5 6 7 2