Разделите данный связанный список на два списка с соотношением размеров p: q.
Опубликовано: 23 Января, 2022
Учитывая связанный список и два целых числа 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
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
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 qvoid 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 listvoid printList(Node* head){ if (head == NULL) return; cout << head->data << " "; printList(head->next);}// Driver codeint 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 approachclass GFG{ // Nodestatic class Node{ int data; Node next; Node(int data) { this.data = data; }}// Function to split the given linked list// into ratio of p and qstatic 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 liststatic void printList(Node head){ if( head == null) return; System.out.print(head.data+" , "); printList(head.next);}// Driver codepublic 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 nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to split the given linked list# into ratio of p and qdef 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 listdef printList(head): if not head: return print("{} ".format(head.data), end ="") printList(head.next)# Driver codehead = 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, 4splitAndPrint(head, p, q) |
C#
// C# implementation of the approachusing 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 qstatic 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 liststatic void printList(Node head){ if( head == null) return; Console.Write(head.data+" "); printList(head.next);}// Driver codepublic 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 */ |
Output:
1 3 5 6 7 2