Dado un entero K y una lista enlazada en la que cada Node almacena un solo carácter. La tarea es unir cada K Nodes consecutivos de la lista enlazada para formar una sola palabra. Finalmente, imprima la string obtenida al unir estas palabras (separadas por espacios).
Ejemplos:
Entrada: List = ‘a’ -> ‘b’ -> ‘c’ ->’d’ -> ‘e’ -> NULL, k = 3 Salida: abc de Los tres primeros Nodes forman la primera palabra
“ abc
”
y los siguientes dos Nodes forman la segunda palabra «de».
Entrada: Lista = ‘a’ -> ‘b’ -> ‘c’ -> ‘d’ -> ‘e’ -> ‘f’ -> NULL, k = 2 Salida: ab
cd ef
Enfoque: La idea es recorrer la lista enlazada y seguir agregando el carácter presente en cada Node a la palabra formada hasta el momento. Lleve un registro de la cantidad de Nodes atravesados y cuando el conteo sea igual a k, agregue la palabra formada hasta ahora a la string resultante, restablezca word a una string vacía y restablezca el conteo a cero. Repita esto hasta que no se recorra toda la lista enlazada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a node
struct Node {
char data;
Node* next;
};
// Function to get a new node
Node* getNode(char data)
{
// Allocate space
Node* newNode = new Node;
// Put in data
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to find string formed by joining words
// obtained by joining k consecutive nodes of
// linked list.
string findKWordString(Node* head, int k)
{
// Stores the final string
string ans = "";
// Keep track of the number of
// nodes traversed
int cnt = 0;
// Stores the word formed by k consecutive
// nodes of the linked list
string word = "";
while (head) {
// Check if k nodes are traversed
// If yes then add the word obtained
// to the result string
if (cnt == k) {
if (ans != "") {
ans = ans + " ";
}
ans = ans + word;
word = "";
cnt = 0;
}
// Add the current character to the word
// formed so far and increase the count
word = word + string(1, head->data);
cnt++;
head = head->next;
}
// Add the final word to the result
// Length of the final word can be less than k
if (ans != " ") {
ans = ans + " ";
}
ans = ans + word;
return ans;
}
// Driver code
int main()
{
// Create list: a -> b -> c -> d -> e
Node* head = getNode('a');
head->next = getNode('b');
head->next->next = getNode('c');
head->next->next->next = getNode('d');
head->next->next->next->next = getNode('e');
int k = 3;
cout << findKWordString(head, k);
return 0;
}
Java
// Java implementation of the approach
class GFG{
// Class of a node
static class Node
{
char data;
Node next;
};
// Function to get a new node
static Node getNode(char data)
{
// Allocate space
Node newNode = new Node();
// Put in data
newNode.data = data;
newNode.next = null;
return newNode;
}
// Function to find string formed by
// joining words obtained by joining
// k consecutive nodes of linked list.
static String findKWordString(Node head, int k)
{
// Stores the final string
String ans = "";
// Keep track of the number of
// nodes traversed
int cnt = 0;
// Stores the word formed by k consecutive
// nodes of the linked list
String word = "";
while (head != null)
{
// Check if k nodes are traversed
// if yes then add the word obtained
// to the result String
if (cnt == k)
{
if (ans != "")
{
ans = (ans + " ");
}
ans = ans + word;
word = "";
cnt = 0;
}
// Add the current character to the word
// formed so far and increase the count
word = word + head.data;
cnt++;
head = head.next;
}
// Add the final word to the result
// Length of the final word can be
// less than k
if (ans != " ")
{
ans = (ans + " ");
}
ans = ans + word;
return ans;
}
// Driver code
public static void main(String[] args)
{
// Create list: a.b.c.d.e
Node head = getNode('a');
head.next = getNode('b');
head.next.next = getNode('c');
head.next.next.next = getNode('d');
head.next.next.next.next = getNode('e');
int k = 3;
System.out.print(findKWordString(head, k));
}
}
// This code is contributed by GauravRajput1
Python3
# Python3 implementation of the approach
# Structure of a node
class Node:
def __init__(self, d):
self.data = d
self.next = None
# Function to find formed by joining words
# obtained by joining k consecutive nodes of
# linked list.
def findKWordString(head,k):
# Stores the final
ans = ""
# Keep track of the number of
# nodes traversed
cnt = 0
# Stores the word formed by k consecutive
# nodes of the linked list
word = ""
while (head):
# Check if k nodes are traversed
# If yes then add the word obtained
# to the result
if (cnt == k):
if (ans != ""):
ans = ans + " "
ans = ans + word
word = ""
cnt = 0
# Add the current character to the word
# formed so far and increase the count
word = word + head.data
cnt += 1
head = head.next
# Add the final word to the result
# Length of the final word can be less than k
if (ans != " "):
ans = ans + " "
ans = ans + word
return ans
# Driver code
if __name__ == '__main__':
#Create list: a . b . c . d . e
head = Node('a')
head.next = Node('b')
head.next.next = Node('c')
head.next.next.next = Node('d')
head.next.next.next.next = Node('e')
k = 3
print(findKWordString(head, k))
# This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG{
// Class of a node
class Node
{
public char data;
public Node next;
};
// Function to get a new node
static Node getNode(char data)
{
// Allocate space
Node newNode = new Node();
// Put in data
newNode.data = data;
newNode.next = null;
return newNode;
}
// Function to find string formed by
// joining words obtained by joining
// k consecutive nodes of linked list.
static String findKWordString(Node head, int k)
{
// Stores the final string
String ans = "";
// Keep track of the number
// of nodes traversed
int cnt = 0;
// Stores the word formed by k
// consecutive nodes of the
// linked list
String word = "";
while (head != null)
{
// Check if k nodes are traversed
// if yes then add the word obtained
// to the result String
if (cnt == k)
{
if (ans != "")
{
ans = (ans + " ");
}
ans = ans + word;
word = "";
cnt = 0;
}
// Add the current character to the word
// formed so far and increase the count
word = word + head.data;
cnt++;
head = head.next;
}
// Add the readonly word to the result
// Length of the readonly word can be
// less than k
if (ans != " ")
{
ans = (ans + " ");
}
ans = ans + word;
return ans;
}
// Driver code
public static void Main(String[] args)
{
// Create list: a.b.c.d.e
Node head = getNode('a');
head.next = getNode('b');
head.next.next = getNode('c');
head.next.next.next = getNode('d');
head.next.next.next.next = getNode('e');
int k = 3;
Console.Write(findKWordString(head, k));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript implementation of the approach
// Class of a node
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Function to get a new node
function getNode( data) {
// Allocate space
var newNode = new Node();
// Put in data
newNode.data = data;
newNode.next = null;
return newNode;
}
// Function to find string formed by
// joining words obtained by joining
// k consecutive nodes of linked list.
function findKWordString(head , k) {
// Stores the final string
var ans = "";
// Keep track of the number of
// nodes traversed
var cnt = 0;
// Stores the word formed by k consecutive
// nodes of the linked list
var word = "";
while (head != null) {
// Check if k nodes are traversed
// if yes then add the word obtained
// to the result String
if (cnt == k) {
if (ans != "") {
ans = (ans + " ");
}
ans = ans + word;
word = "";
cnt = 0;
}
// Add the current character to the word
// formed so far and increase the count
word = word + head.data;
cnt++;
head = head.next;
}
// Add the final word to the result
// Length of the final word can be
// less than k
if (ans != " ") {
ans = (ans + " ");
}
ans = ans + word;
return ans;
}
// Driver code
// Create list: a.b.c.d.e
var head = getNode('a');
head.next = getNode('b');
head.next.next = getNode('c');
head.next.next.next = getNode('d');
head.next.next.next.next = getNode('e');
var k = 3;
document.write(findKWordString(head, k));
// This code contributed by aashish1995
</script>
Producción:
abc de
Complejidad temporal: O(N)
Espacio auxiliar: O(1)