Dada una lista enlazada individualmente, intercambie el k-ésimo Node desde el principio con el k-ésimo Node desde el final. No se permite el intercambio de datos, solo se deben cambiar los punteros. Este requisito puede ser lógico en muchas situaciones en las que la parte de datos de la lista enlazada es enorme (por ejemplo, la línea de detalles del estudiante Nombre, RollNo, Dirección, etc.). Los punteros siempre son fijos (4 bytes para la mayoría de los compiladores).
Ejemplo:
Input: 1 -> 2 -> 3 -> 4 -> 5, K = 2 Output: 1 -> 4 -> 3 -> 2 -> 5 Explanation: The 2nd node from 1st is 2 and 2nd node from last is 4, so swap them. Input: 1 -> 2 -> 3 -> 4 -> 5, K = 5 Output: 5 -> 2 -> 3 -> 4 -> 1 Explanation: The 5th node from 1st is 5 and 5th node from last is 1, so swap them.
Ilustración:
Enfoque: La idea es muy simple: encuentre el k-ésimo Node desde el principio y el k-ésimo Node desde el último es n-k+1-ésimo Node desde el principio. Intercambia ambos Nodes.
Sin embargo, hay algunos casos de esquina, que deben ser manejados
- Y está al lado de X
- X está al lado de Y
- X e Y son iguales
- X e Y no existen (k es más que el número de Nodes en la lista vinculada)
A continuación se muestra la implementación del enfoque anterior.
C++
// A C++ program to swap Kth node from beginning with kth
// node from end
#include <bits/stdc++.h>
using namespace std;
// A Linked List node
typedef struct Node {
int data;
struct Node* next;
} Node;
// Utility function to insert a node at the beginning
void push(Node** head_ref, int new_data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Utility function for displaying linked list */
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
/* Utility function for calculating
length of linked list */
int countNodes(struct Node* s)
{
int count = 0;
while (s != NULL) {
count++;
s = s->next;
}
return count;
}
// Utility function for calculating length of linked list
void swapKth(struct Node** head_ref, int k)
{
// Count nodes in linked list
int n = countNodes(*head_ref);
// Check if k is valid
if (n < k)
return;
// If x (kth node from start) and y(kth node from end)
// are same
if (2 * k - 1 == n)
return;
// Find the kth node from the beginning of the linked
// list. We also find previous of kth node because we
// need to update next pointer of the previous.
Node* x = *head_ref;
Node* x_prev = NULL;
for (int i = 1; i < k; i++) {
x_prev = x;
x = x->next;
}
// Similarly, find the kth node from end and its
// previous. kth node from end is (n-k+1)th node from
// beginning
Node* y = *head_ref;
Node* y_prev = NULL;
for (int i = 1; i < n - k + 1; i++) {
y_prev = y;
y = y->next;
}
// If x_prev exists, then new next of it will be y.
// Consider the case when y->next is x, in this case,
// x_prev and y are same. So the statement "x_prev->next
// = y" creates a self loop. This self loop will be
// broken when we change y->next.
if (x_prev)
x_prev->next = y;
// Same thing applies to y_prev
if (y_prev)
y_prev->next = x;
// Swap next pointers of x and y. These statements also
// break self loop if x->next is y or y->next is x
Node* temp = x->next;
x->next = y->next;
y->next = temp;
// Change head pointers when k is 1 or n
if (k == 1)
*head_ref = y;
if (k == n)
*head_ref = x;
}
// Driver program to test above functions
int main()
{
// Let us create the following linked list for testing
// 1->2->3->4->5->6->7->8
struct Node* head = NULL;
for (int i = 8; i >= 1; i--)
push(&head, i);
cout << "Original Linked List: ";
printList(head);
for (int k = 1; k < 9; k++) {
swapKth(&head, k);
cout << "\nModified List for k = " << k << endl;
printList(head);
}
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// A C program to swap Kth node from beginning with kth
// node from end
#include <stdio.h>
#include <stdlib.h>
// A Linked List node
typedef struct Node {
int data;
struct Node* next;
} Node;
// Utility function to insert a node at the beginning
void push(Node** head_ref, int new_data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Utility function for displaying linked list
void printList(Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
// Utility function for calculating length of linked list
int countNodes(Node* s)
{
int count = 0;
while (s != NULL) {
count++;
s = s->next;
}
return count;
}
// Function for swapping kth nodes from both ends of linked
// list
void swapKth(Node** head_ref, int k)
{
// Count nodes in linked list
int n = countNodes(*head_ref);
// Check if k is valid
if (n < k)
return;
// If x (kth node from start) and y(kth node from end)
// are same
if (2 * k - 1 == n)
return;
// Find the kth node from the beginning of the linked
// list. We also find previous of kth node because we
// need to update next pointer of the previous.
Node* x = *head_ref;
Node* x_prev = NULL;
for (int i = 1; i < k; i++) {
x_prev = x;
x = x->next;
}
// Similarly, find the kth node from end and its
// previous. kth node from end is (n-k+1)th node from
// beginning
Node* y = *head_ref;
Node* y_prev = NULL;
for (int i = 1; i < n - k + 1; i++) {
y_prev = y;
y = y->next;
}
// If x_prev exists, then new next of it will be y.
// Consider the case when y->next is x, in this case,
// x_prev and y are same. So the statement "x_prev->next
// = y" creates a self loop. This self loop will be
// broken when we change y->next.
if (x_prev)
x_prev->next = y;
// Same thing applies to y_prev
if (y_prev)
y_prev->next = x;
// Swap next pointers of x and y. These statements also
// break self loop if x->next is y or y->next is x
Node* temp = x->next;
x->next = y->next;
y->next = temp;
// Change head pointers when k is 1 or n
if (k == 1)
*head_ref = y;
if (k == n)
*head_ref = x;
}
// Driver program to test above functions
int main()
{
// Let us create the following linked list for testing
// 1->2->3->4->5->6->7->8
Node* head = NULL;
for (int i = 8; i >= 1; i--)
push(&head, i);
printf("Original Linked List: ");
printList(head);
for (int k = 1; k < 9; k++) {
swapKth(&head, k);
printf("\nModified List for k = %d\n", k);
printList(head);
}
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// A Java program to swap kth node from the beginning with
// kth node from the end
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
class LinkedList {
Node head;
// Utility function to insert a node at the beginning
void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
/* Utility function for displaying linked list */
void printList()
{
Node node = head;
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println("");
}
// Utility function for calculating length of linked
// list
int countNodes()
{
int count = 0;
Node s = head;
while (s != null) {
count++;
s = s.next;
}
return count;
}
// Function for swapping kth nodes from both ends of
// linked list
void swapKth(int k)
{
// Count nodes in linked list
int n = countNodes();
// Check if k is valid
if (n < k)
return;
// If x (kth node from start) and
// y(kth node from end) are same
if (2 * k - 1 == n)
return;
// Find the kth node from beginning of linked list.
// We also find previous of kth node because we need
// to update next pointer of the previous.
Node x = head;
Node x_prev = null;
for (int i = 1; i < k; i++) {
x_prev = x;
x = x.next;
}
// Similarly, find the kth node from end and its
// previous. kth node from end is (n-k+1)th node
// from beginning
Node y = head;
Node y_prev = null;
for (int i = 1; i < n - k + 1; i++) {
y_prev = y;
y = y.next;
}
// If x_prev exists, then new next of it will be y.
// Consider the case when y->next is x, in this
// case, x_prev and y are same. So the statement
// "x_prev->next = y" creates a self loop. This self
// loop will be broken when we change y->next.
if (x_prev != null)
x_prev.next = y;
// Same thing applies to y_prev
if (y_prev != null)
y_prev.next = x;
// Swap next pointers of x and y. These statements
// also break self loop if x->next is y or y->next
// is x
Node temp = x.next;
x.next = y.next;
y.next = temp;
// Change head pointers when k is 1 or n
if (k == 1)
head = y;
if (k == n)
head = x;
}
// Driver code to test above
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
for (int i = 8; i >= 1; i--)
llist.push(i);
System.out.print("Original linked list: ");
llist.printList();
System.out.println("");
for (int i = 1; i < 9; i++) {
llist.swapKth(i);
System.out.println("Modified List for k = " + i);
llist.printList();
System.out.println("");
}
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
"""
A Python3 program to swap kth node from
the beginning with kth node from the end
"""
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
class LinkedList:
def __init__(self, *args, **kwargs):
self.head = Node(None)
"""
Utility function to insert a node at the beginning
@args:
data: value of node
"""
def push(self, data):
node = Node(data)
node.next = self.head
self.head = node
# Print linked list
def printList(self):
node = self.head
while node.next is not None:
print(node.data, end = " ")
node = node.next
# count number of node in linked list
def countNodes(self):
count = 0
node = self.head
while node.next is not None:
count += 1
node = node.next
return count
"""
Function for swapping kth nodes from
both ends of linked list
"""
def swapKth(self, k):
# Count nodes in linked list
n = self.countNodes()
# check if k is valid
if n<k:
return
"""
If x (kth node from start) and
y(kth node from end) are same
"""
if (2 * k - 1) == n:
return
"""
Find the kth node from beginning of linked list.
We also find previous of kth node because we need
to update next pointer of the previous.
"""
x = self.head
x_prev = Node(None)
for i in range(k - 1):
x_prev = x
x = x.next
"""
Similarly, find the kth node from end and its
previous. kth node from end is (n-k + 1)th node
from beginning
"""
y = self.head
y_prev = Node(None)
for i in range(n - k):
y_prev = y
y = y.next
"""
If x_prev exists, then new next of it will be y.
Consider the case when y->next is x, in this case,
x_prev and y are same. So the statement
"x_prev->next = y" creates a self loop. This self
loop will be broken when we change y->next.
"""
if x_prev is not None:
x_prev.next = y
# Same thing applies to y_prev
if y_prev is not None:
y_prev.next = x
"""
Swap next pointers of x and y. These statements
also break self loop if x->next is y or y->next
is x
"""
temp = x.next
x.next = y.next
y.next = temp
# Change head pointers when k is 1 or n
if k == 1:
self.head = y
if k == n:
self.head = x
# Driver Code
llist = LinkedList()
for i in range(8, 0, -1):
llist.push(i)
llist.printList()
for i in range(1, 9):
llist.swapKth(i)
print("Modified List for k = ", i)
llist.printList()
print("\n")
# This code is contributed by Pulkit
C#
// C# program to swap kth node from the beginning with
// kth node from the end
using System;
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
public class LinkedList {
Node head;
/* Utility function to insert
a node at the beginning */
void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
/* Utility function for displaying linked list */
void printList()
{
Node node = head;
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
Console.WriteLine("");
}
/* Utility function for calculating
length of linked list */
int countNodes()
{
int count = 0;
Node s = head;
while (s != null) {
count++;
s = s.next;
}
return count;
}
/* Function for swapping kth nodes from
both ends of linked list */
void swapKth(int k)
{
// Count nodes in linked list
int n = countNodes();
// Check if k is valid
if (n < k)
return;
// If x (kth node from start) and y(kth node from end)
// are same
if (2 * k - 1 == n)
return;
// Find the kth node from beginning of linked list.
// We also find previous of kth node because we need
// to update next pointer of the previous.
Node x = head;
Node x_prev = null;
for (int i = 1; i < k; i++) {
x_prev = x;
x = x.next;
}
// Similarly, find the kth node from end and its
// previous. kth node from end is (n-k+1)th node
// from beginning
Node y = head;
Node y_prev = null;
for (int i = 1; i < n - k + 1; i++) {
y_prev = y;
y = y.next;
}
// If x_prev exists, then new next of it will be y.
// Consider the case when y->next is x, in this case,
// x_prev and y are same. So the statement
// "x_prev->next = y" creates a self loop. This self
// loop will be broken when we change y->next.
if (x_prev != null)
x_prev.next = y;
// Same thing applies to y_prev
if (y_prev != null)
y_prev.next = x;
// Swap next pointers of x and y. These statements
// also break self loop if x->next is y or y->next
// is x
Node temp = x.next;
x.next = y.next;
y.next = temp;
// Change head pointers when k is 1 or n
if (k == 1)
head = y;
if (k == n)
head = x;
}
// Driver code
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
for (int i = 8; i >= 1; i--)
llist.push(i);
Console.Write("Original linked list: ");
llist.printList();
Console.WriteLine("");
for (int i = 1; i < 9; i++) {
llist.swapKth(i);
Console.WriteLine("Modified List for k = " + i);
llist.printList();
Console.WriteLine("");
}
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// A javascript program to swap kth
// node from the beginning with
// kth node from the end
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
var head;
/*
* Utility function to insert a node at the beginning
*/
function push(new_data) {
new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
/* Utility function for displaying linked list */
function printList()
{
node = head;
while (node != null)
{
document.write(node.data + " ");
node = node.next;
}
document.write("");
}
/*
* Utility function for calculating length of linked list
*/
function countNodes()
{
var count = 0;
s = head;
while (s != null)
{
count++;
s = s.next;
}
return count;
}
/*
* Function for swapping kth nodes from both ends of linked list
*/
function swapKth(k)
{
// Count nodes in linked list
var n = countNodes();
// Check if k is valid
if (n < k)
return;
// If x (kth node from start) and
// y(kth node from end) are same
if (2 * k - 1 == n)
return;
// Find the kth node from beginning of linked list.
// We also find previous of kth node because we need
// to update next pointer of the previous.
x = head;
x_prev = null;
for (i = 1; i < k; i++)
{
x_prev = x;
x = x.next;
}
// Similarly, find the kth node from end and its
// previous. kth node from end is (n-k+1)th node
// from beginning
y = head;
y_prev = null;
for (i = 1; i < n - k + 1; i++)
{
y_prev = y;
y = y.next;
}
// If x_prev exists, then new next of it will be y.
// Consider the case when y->next is x, in this case,
// x_prev and y are same. So the statement
// "x_prev->next = y" creates a self loop. This self
// loop will be broken when we change y->next.
if (x_prev != null)
x_prev.next = y;
// Same thing applies to y_prev
if (y_prev != null)
y_prev.next = x;
// Swap next pointers of x and y. These statements
// also break self loop if x->next is y or y->next
// is x
temp = x.next;
x.next = y.next;
y.next = temp;
// Change head pointers when k is 1 or n
if (k == 1)
head = y;
if (k == n)
head = x;
}
// Driver code to test above
for (let i = 8; i >= 1; i--)
push(i);
document.write("Original linked list: <br/>");
printList();
document.write("<br/>");
for (let i = 1; i < 9; i++)
{
swapKth(i);
document.write("Modified List for k = " + i + "<br/>");
printList();
document.write("<br/>");
}
// This code is contributed by gauravrajput1
</script>
Producción
Original Linked List: 1 2 3 4 5 6 7 8 Modified List for k = 1 8 2 3 4 5 6 7 1 Modified List for k = 2 8 7 3 4 5 6 2 1 Modified List for k = 3 8 7 6 4 5 3 2 1 Modified List for k = 4 8 7 6 5 4 3 2 1 Modified List for k = 5 8 7 6 4 5 3 2 1 Modified List for k = 6 8 7 3 4 5 6 2 1 Modified List for k = 7 8 2 3 4 5 6 7 1 Modified List for k = 8 1 2 3 4 5 6 7 8
Análisis de Complejidad:
- Complejidad temporal: O(n), donde n es la longitud de la lista.
Se necesita un recorrido de la lista. - Espacio Auxiliar: O(1).
No se requiere espacio adicional.
Tenga en cuenta que el código anterior ejecuta tres bucles separados para contar Nodes, encontrar x y x anterior, y encontrar y e y_prev. Estas tres cosas se pueden hacer en un solo ciclo. El código usa tres bucles para mantener las cosas simples y legibles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA