Dadas dos listas enlazadas individualmente, encuentre el sufijo común más largo de dos listas enlazadas. Si no hay caracteres comunes que sean sufijos, devuelve la longitud mínima de las dos listas enlazadas.
Ejemplos:
Input : list1 = w -> a -> l -> k -> i -> n -> g
list2 = l -> i -> s -> t -> e -> n -> i -> n -> g
Output :i -> n -> g
Input : list1 = p -> a -> r -> t -> y
list2 = p -> a -> r -> t -> y -> i -> n -> g
Output :p -> a -> r -> t -> y
Una solución simple es usar arreglos auxiliares para almacenar listas enlazadas. Luego imprima el sufijo común más largo de dos arrays.
La solución anterior requiere espacio adicional. Podemos ahorrar espacio haciendo primero el reverso de ambas listas enlazadas. Después de invertir, podemos encontrar fácilmente la longitud del prefijo común más largo. Invirtiendo de nuevo para recuperar las listas originales.
Un punto importante aquí es el orden de los elementos. Necesitamos imprimir los Nodes desde el n-ésimo hasta el final. Usamos los Nodes de conteo e impresión encontrados anteriores en el orden requerido usando el enfoque de dos punteros.
C++
// C++ program to find the Longest Common
// suffix in linked lists
#include <bits/stdc++.h>
using namespace std;
/* Linked list node */
struct Node
{
char data;
struct Node* next;
};
/* Function to insert a node at the beginning of
the linked list */
void push(struct Node **head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
/* Function to reverse the linked list */
struct Node *reverseList(struct Node *head_ref)
{
struct Node *current, *prev, *next;
current = head_ref;
prev = NULL;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
// Utility function to print last n nodes
void printLastNNode(struct Node* head, int n)
{
// if n == 0
if (n <= 0)
return;
// Move reference pointer n positions ahead
struct Node* ref_ptr = head;
while (ref_ptr != NULL && n--)
ref_ptr = ref_ptr->next;
// Now move main and reference pointers at
// same speed. By the end of this loop,
// reference pointer would point to end and
// main pointer would point to n-th node
// from end.
Node *main_ptr = head;
while (ref_ptr != NULL) {
main_ptr = main_ptr->next;
ref_ptr = ref_ptr->next;
}
// Print last n nodes.
while (main_ptr != NULL)
{
cout << main_ptr->data;
main_ptr = main_ptr->next;
}
}
// Prints the Longest Common suffix in
// linked lists
void longestCommSuffix(Node *h1, Node *h2)
{
// Reverse Both Linked list
h1 = reverseList(h1);
h2 = reverseList(h2);
// Now we print common nodes from head
Node *temp1 = h1, *temp2 = h2;
int count = 0;
while (temp1!=NULL&&temp2!=NULL)
{
// If a node is not common, break
if (temp1 -> data != temp2 -> data)
break;
// Keep printing while there are
// common nodes.
count++;
temp1 = temp1 -> next;
temp2 = temp2 -> next;
}
// Reversing linked lists to retain
// original lists.
h1 = reverseList(h1);
h2 = reverseList(h2);
printLastNNode(h1, count);
}
// Driver program to test above
int main()
{
struct Node *h1 = NULL, *h2 = NULL;
// creating the 1 linked list
push(&h1,'g');
push(&h1,'n');
push(&h1,'i');
push(&h1,'k');
push(&h1,'l');
push(&h1,'a');
push(&h1,'w');
// creating the 2 linked list
push(&h2,'g');
push(&h2,'n');
push(&h2,'i');
push(&h2,'n');
push(&h2,'e');
push(&h2,'t');
push(&h2,'s');
push(&h2,'i');
push(&h2,'l');
longestCommSuffix(h1, h2);
return 0;
}
Java
// Java program to find the Longest Common
// suffix in linked lists
import java.util.*;
class GFG
{
/* Linked list node */
static class Node
{
int data;
Node next;
};
static Node h1,h2;
/* Function to insert a node at the beginning
of the linked list */
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
/* Function to reverse the linked list */
static Node reverseList(Node head_ref)
{
Node current, prev, next;
current = head_ref;
prev = null;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
// Utility function to print last n nodes
static void printLastNNode(Node head, int n)
{
// if n == 0
if (n <= 0)
return;
// Move reference pointer n positions ahead
Node ref_ptr = head;
while (ref_ptr != null && n-- > 0)
ref_ptr = ref_ptr.next;
// Now move main and reference pointers at
// same speed. By the end of this loop,
// reference pointer would point to end and
// main pointer would point to n-th node
// from end.
Node main_ptr = head;
while (ref_ptr != null)
{
main_ptr = main_ptr.next;
ref_ptr = ref_ptr.next;
}
// Print last n nodes.
while (main_ptr != null)
{
System.out.print((char)(main_ptr.data));
main_ptr = main_ptr.next;
}
}
// Prints the Longest Common suffix in
// linked lists
static void longestCommSuffix()
{
// Reverse Both Linked list
h1 = reverseList(h1);
h2 = reverseList(h2);
// Now we print common nodes from head
Node temp1 = h1, temp2 = h2;
int count = 0;
while (temp1 != null && temp2 != null)
{
// If a node is not common, break
if (temp1 . data != temp2 . data)
break;
// Keep printing while there are
// common nodes.
count++;
temp1 = temp1 . next;
temp2 = temp2 . next;
}
// Reversing linked lists to retain
// original lists.
h1 = reverseList(h1);
h2 = reverseList(h2);
printLastNNode(h1, count);
}
// Driver Code
public static void main(String[] args)
{
h1 = null; h2 = null;
// creating the 1 linked list
h1 = push(h1, 'g');
h1 = push(h1, 'n');
h1 = push(h1, 'i');
h1 = push(h1, 'k');
h1 = push(h1, 'l');
h1 = push(h1, 'a');
h1 = push(h1, 'w');
// creating the 2 linked list
h2 = push(h2, 'g');
h2 = push(h2, 'n');
h2 = push(h2, 'i');
h2 = push(h2, 'n');
h2 = push(h2, 'e');
h2 = push(h2, 't');
h2 = push(h2, 's');
h2 = push(h2, 'i');
h2 = push(h2, 'l');
longestCommSuffix();
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find the Longest Common # suffix in linked lists # Link list node class Node: def __init__(self, data): self.data = data self.next = None # Function to insert a node at the # beginning of the linked list def push( head_ref, new_data): new_node = Node(new_data) new_node.next = head_ref head_ref = new_node return head_ref # Function to reverse the linked list def reverseList(head_ref): next = None current = head_ref prev = None while (current != None): next = current.next current.next = prev prev = current current = next return prev # Utility function to print last n nodes def printLastNNode(head, n): # If n == 0 if (n <= 0): return # Move reference pointer n positions ahead ref_ptr = head while (ref_ptr != None and n != 0): n -= 1 ref_ptr = ref_ptr.next # Now move main and reference pointers at # same speed. By the end of this loop, # reference pointer would point to end and # main pointer would point to n-th node # from end. main_ptr = head while (ref_ptr != None): main_ptr = main_ptr.next ref_ptr = ref_ptr.next # Print last n nodes. while (main_ptr != None): print(main_ptr.data, end = '') main_ptr = main_ptr.next # Prints the Longest Common suffix in # linked lists def longestCommSuffix(h1, h2): # Reverse Both Linked list h1 = reverseList(h1) h2 = reverseList(h2) # Now we print common nodes from head temp1 = h1 temp2 = h2 count = 0 while (temp1 != None and temp2 != None): # If a node is not common, break if (temp1.data != temp2.data): break # Keep printing while there are # common nodes. count += 1 temp1 = temp1.next temp2 = temp2.next # Reversing linked lists to retain # original lists. h1 = reverseList(h1) h2 = reverseList(h2) printLastNNode(h1, count) # Driver code if __name__=='__main__': h1 = None h2 = None # Creating the 1 linked list h1 = push(h1, 'g') h1 = push(h1, 'n') h1 = push(h1, 'i') h1 = push(h1, 'k') h1 = push(h1, 'l') h1 = push(h1, 'a') h1 = push(h1, 'w') # Creating the 2 linked list h2 = push(h2, 'g') h2 = push(h2, 'n') h2 = push(h2, 'i') h2 = push(h2, 'n') h2 = push(h2, 'e') h2 = push(h2, 't') h2 = push(h2, 's') h2 = push(h2, 'i') h2 = push(h2, 'l') longestCommSuffix(h1, h2) # This code is contributed by rutvik_56
C#
// C# program to find the Longest Common
// suffix in linked lists
using System;
class GFG
{
/* Linked list node */
public class Node
{
public int data;
public Node next;
};
static Node h1, h2;
/* Function to insert a node
at the beginning of the linked list */
static Node push(Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
/* Function to reverse the linked list */
static Node reverseList(Node head_ref)
{
Node current, prev, next;
current = head_ref;
prev = null;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
// Utility function to print last n nodes
static void printLastNNode(Node head, int n)
{
// if n == 0
if (n <= 0)
return;
// Move reference pointer n positions ahead
Node ref_ptr = head;
while (ref_ptr != null && n-- > 0)
ref_ptr = ref_ptr.next;
// Now move main and reference pointers at
// same speed. By the end of this loop,
// reference pointer would point to end and
// main pointer would point to n-th node
// from end.
Node main_ptr = head;
while (ref_ptr != null)
{
main_ptr = main_ptr.next;
ref_ptr = ref_ptr.next;
}
// Print last n nodes.
while (main_ptr != null)
{
Console.Write((char)(main_ptr.data));
main_ptr = main_ptr.next;
}
}
// Prints the Longest Common suffix in
// linked lists
static void longestCommSuffix()
{
// Reverse Both Linked list
h1 = reverseList(h1);
h2 = reverseList(h2);
// Now we print common nodes from head
Node temp1 = h1, temp2 = h2;
int count = 0;
while (temp1 != null && temp2 != null)
{
// If a node is not common, break
if (temp1 . data != temp2 . data)
break;
// Keep printing while there are
// common nodes.
count++;
temp1 = temp1 . next;
temp2 = temp2 . next;
}
// Reversing linked lists to retain
// original lists.
h1 = reverseList(h1);
h2 = reverseList(h2);
printLastNNode(h1, count);
}
// Driver Code
public static void Main(String[] args)
{
h1 = null; h2 = null;
// creating the 1 linked list
h1 = push(h1, 'g');
h1 = push(h1, 'n');
h1 = push(h1, 'i');
h1 = push(h1, 'k');
h1 = push(h1, 'l');
h1 = push(h1, 'a');
h1 = push(h1, 'w');
// creating the 2 linked list
h2 = push(h2, 'g');
h2 = push(h2, 'n');
h2 = push(h2, 'i');
h2 = push(h2, 'n');
h2 = push(h2, 'e');
h2 = push(h2, 't');
h2 = push(h2, 's');
h2 = push(h2, 'i');
h2 = push(h2, 'l');
longestCommSuffix();
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find the Longest Common
// suffix in linked lists
/* Linked list node */
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
};
var h1, h2;
/* Function to insert a node
at the beginning of the linked list */
function push(head_ref, new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
/* Function to reverse the linked list */
function reverseList(head_ref)
{
var current, prev, next;
current = head_ref;
prev = null;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
// Utility function to print last n nodes
function printLastNNode(head, n)
{
// if n == 0
if (n <= 0)
return;
// Move reference pointer n positions ahead
var ref_ptr = head;
while (ref_ptr != null && n-- > 0)
ref_ptr = ref_ptr.next;
// Now move main and reference pointers at
// same speed. By the end of this loop,
// reference pointer would point to end and
// main pointer would point to n-th node
// from end.
var main_ptr = head;
while (ref_ptr != null)
{
main_ptr = main_ptr.next;
ref_ptr = ref_ptr.next;
}
// Print last n nodes.
while (main_ptr != null)
{
document.write((main_ptr.data));
main_ptr = main_ptr.next;
}
}
// Prints the Longest Common suffix in
// linked lists
function longestCommSuffix()
{
// Reverse Both Linked list
h1 = reverseList(h1);
h2 = reverseList(h2);
// Now we print common nodes from head
var temp1 = h1, temp2 = h2;
var count = 0;
while (temp1 != null && temp2 != null)
{
// If a node is not common, break
if (temp1 . data != temp2 . data)
break;
// Keep printing while there are
// common nodes.
count++;
temp1 = temp1 . next;
temp2 = temp2 . next;
}
// Reversing linked lists to retain
// original lists.
h1 = reverseList(h1);
h2 = reverseList(h2);
printLastNNode(h1, count);
}
// Driver Code
h1 = null; h2 = null;
// creating the 1 linked list
h1 = push(h1, 'g');
h1 = push(h1, 'n');
h1 = push(h1, 'i');
h1 = push(h1, 'k');
h1 = push(h1, 'l');
h1 = push(h1, 'a');
h1 = push(h1, 'w');
// creating the 2 linked list
h2 = push(h2, 'g');
h2 = push(h2, 'n');
h2 = push(h2, 'i');
h2 = push(h2, 'n');
h2 = push(h2, 'e');
h2 = push(h2, 't');
h2 = push(h2, 's');
h2 = push(h2, 'i');
h2 = push(h2, 'l');
longestCommSuffix();
</script>
Producción:
ing
Complejidad de tiempo : O(N)