Dada la lista circular enlazada, intercambie el primer y el último Node. La tarea debe realizarse con un solo Node adicional, no puede declarar más de un Node adicional y tampoco puede declarar ninguna otra variable temporal.
Nota: Node adicional significa la necesidad de un Node para atravesar una lista.
Ejemplos:
Input : 5 4 3 2 1 Output : 1 4 3 2 5 Input : 6 1 2 3 4 5 6 7 8 9 Output : 9 1 2 3 4 5 6 7 8 6
Método 1: (Al cambiar los enlaces del primer y último Node)
Primero encontramos un puntero al anterior al último Node. Sea este Node p. Ahora cambiamos los siguientes enlaces para que se intercambien el último y el primer Node.
C++
// CPP program to exchange first and
// last node in circular linked list
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* addToEmpty(struct Node* head, int data)
{
// This function is only for empty list
if (head != NULL)
return head;
// Creating a node dynamically.
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp->data = data;
head = temp;
// Creating the link.
head->next = head;
return head;
}
struct Node* addBegin(struct Node* head, int data)
{
if (head == NULL)
return addToEmpty(head, data);
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = head->next;
head->next = temp;
return head;
}
/* function for traversing the list */
void traverse(struct Node* head)
{
struct Node* p;
// If list is empty, return.
if (head == NULL) {
cout << "List is empty." << endl;
return;
}
// Pointing to first Node of the list.
p = head;
// Traversing the list.
do {
cout << p->data << " ";
p = p->next;
} while (p != head);
}
/* Function to exchange first and last node*/
struct Node* exchangeNodes(struct Node* head)
{
// If list is of length 2
if (head->next->next == head) {
head = head->next;
return head;
}
// Find pointer to previous of last node
struct Node* p = head;
while (p->next->next != head)
p = p->next;
/* Exchange first and last nodes using
head and p */
p->next->next = head->next;
head->next = p->next;
p->next = head;
head = head->next;
return head;
}
// Driven Program
int main()
{
int i;
struct Node* head = NULL;
head = addToEmpty(head, 6);
for (i = 5; i > 0; i--)
head = addBegin(head, i);
cout << "List Before: ";
traverse(head);
cout << endl;
cout << "List After: ";
head = exchangeNodes(head);
traverse(head);
return 0;
}
Java
// Java program to exchange
// first and last node in
// circular linked list
class GFG {
static class Node {
int data;
Node next;
};
static Node addToEmpty(Node head, int data)
{
// This function is only
// for empty list
if (head != null)
return head;
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
head = temp;
// Creating the link.
head.next = head;
return head;
}
static Node addBegin(Node head, int data)
{
if (head == null)
return addToEmpty(head, data);
Node temp = new Node();
temp.data = data;
temp.next = head.next;
head.next = temp;
return head;
}
// function for traversing the list
static void traverse(Node head)
{
Node p;
// If list is empty, return.
if (head == null) {
System.out.print("List is empty.");
return;
}
// Pointing to first
// Node of the list.
p = head;
// Traversing the list.
do {
System.out.print(p.data + " ");
p = p.next;
} while (p != head);
}
// Function to exchange
// first and last node
static Node exchangeNodes(Node head)
{
// If list is of length 2
if (head.next.next == head) {
head = head.next;
return head;
}
// Find pointer to previous
// of last node
Node p = head;
while (p.next.next != head)
p = p.next;
// Exchange first and last
// nodes using head and p
p.next.next = head.next;
head.next = p.next;
p.next = head;
head = head.next;
return head;
}
// Driver Code
public static void main(String args[])
{
int i;
Node head = null;
head = addToEmpty(head, 6);
for (i = 5; i > 0; i--)
head = addBegin(head, i);
System.out.print("List Before: ");
traverse(head);
System.out.println();
System.out.print("List After: ");
head = exchangeNodes(head);
traverse(head);
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python3 program to exchange first and
# last node in circular linked list
import math
class Node:
def __init__(self, data):
self.data = data
self.next = None
def addToEmpty(head, data):
# This function is only for empty list
if (head != None):
return head
# Creating a node dynamically.
temp = Node(data)
# Assigning the data.
temp.data = data
head = temp
# Creating the link.
head.next = head
return head
def addBegin(head, data):
if (head == None):
return addToEmpty(head, data)
temp = Node(data)
temp.data = data
temp.next = head.next
head.next = temp
return head
# function for traversing the list
def traverse(head):
# If list is empty, return.
if (head == None):
print("List is empty.")
return
# Pointing to first Node of the list.
p = head
print(p.data, end=" ")
p = p.next
# Traversing the list.
while(p != head):
print(p.data, end=" ")
p = p.next
def exchangeNodes(head):
# Cases Handled: Linked List either empty or containing single node.
if head == None or head.next == head:
return head
# Cases Handled: Linked List containing only two nodes
elif head.next.next == head:
head = head.next
return head
# Cases Handled: Linked List containing multiple nodes
else:
prev = None
curr = head
temp = head
# finding last and second last nodes in linkedlist list
while curr.next != head:
prev = curr
curr = curr.next
# point the last node to second node of the list
curr.next = temp.next
# point the second last node to first node
prev.next = temp
# point the end of node to start ( make linked list circular )
temp.next = curr
# mark the starting of linked list
head = curr
return head
# Driver Code
if __name__ == '__main__':
head = None
head = addToEmpty(head, 6)
for x in range(5, 0, -1):
head = addBegin(head, x)
print("List Before: ", end="")
traverse(head)
print()
print("List After: ", end="")
head = exchangeNodes(head)
traverse(head)
# This code is contributed by Srathore
# Improved by Vinay Kumar (vinaykumar71)
C#
// C# program to exchange
// first and last node in
// circular linked list
using System;
public class GFG {
class Node {
public int data;
public Node next;
};
static Node addToEmpty(Node head, int data)
{
// This function is only
// for empty list
if (head != null)
return head;
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
head = temp;
// Creating the link.
head.next = head;
return head;
}
static Node addBegin(Node head, int data)
{
if (head == null)
return addToEmpty(head, data);
Node temp = new Node();
temp.data = data;
temp.next = head.next;
head.next = temp;
return head;
}
// function for traversing the list
static void traverse(Node head)
{
Node p;
// If list is empty, return.
if (head == null) {
Console.Write("List is empty.");
return;
}
// Pointing to first
// Node of the list.
p = head;
// Traversing the list.
do {
Console.Write(p.data + " ");
p = p.next;
} while (p != head);
}
// Function to exchange
// first and last node
static Node exchangeNodes(Node head)
{
// If list is of length 2
if (head.next.next == head) {
head = head.next;
return head;
}
// Find pointer to previous
// of last node
Node p = head;
while (p.next.next != head)
p = p.next;
// Exchange first and last
// nodes using head and p
p.next.next = head.next;
head.next = p.next;
p.next = head;
head = head.next;
return head;
}
// Driver Code
public static void Main()
{
int i;
Node head = null;
head = addToEmpty(head, 6);
for (i = 5; i > 0; i--)
head = addBegin(head, i);
Console.Write("List Before: ");
traverse(head);
Console.WriteLine();
Console.Write("List After: ");
head = exchangeNodes(head);
traverse(head);
}
}
/* This code is contributed PrinciRaj1992 */
Javascript
<script>
// javascript program to exchange
// first and last node in
// circular linked list
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
function addToEmpty(head , data) {
// This function is only
// for empty list
if (head != null)
return head;
// Creating a node dynamically.
var temp = new Node();
// Assigning the data.
temp.data = data;
head = temp;
// Creating the link.
head.next = head;
return head;
}
function addBegin(head , data) {
if (head == null)
return addToEmpty(head, data);
var temp = new Node();
temp.data = data;
temp.next = head.next;
head.next = temp;
return head;
}
// function for traversing the list
function traverse(head) {
var p;
// If list is empty, return.
if (head == null) {
document.write("List is empty.");
return;
}
// Pointing to first
// Node of the list.
p = head;
// Traversing the list.
do {
document.write(p.data + " ");
p = p.next;
} while (p != head);
}
// Function to exchange
// first and last node
function exchangeNodes(head) {
// If list is of length 2
if (head.next.next == head) {
head = head.next;
return head;
}
// Find pointer to previous
// of last node
var p = head;
while (p.next.next != head)
p = p.next;
// Exchange first and last
// nodes using head and p
p.next.next = head.next;
head.next = p.next;
p.next = head;
head = head.next;
return head;
}
// Driver Code
var i;
var head = null;
head = addToEmpty(head, 6);
for (i = 5; i > 0; i--)
head = addBegin(head, i);
document.write("List Before: ");
traverse(head);
document.write("<br/>");
document.write("List After: ");
head = exchangeNodes(head);
traverse(head);
// This code is contributed by umadevi9616
</script>
Producción
List Before: 6 1 2 3 4 5 List After: 5 1 2 3 4 6
Método 2: (Intercambiando valores del primer y último Node)
Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Algoritmo:
- Recorra la lista y encuentre el último Node (cola).
- Intercambiar datos de cabeza y cola.
A continuación se muestra la implementación del algoritmo:
C++
// CPP program to exchange first and
// last node in circular linked list
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* addToEmpty(struct Node* head, int data)
{
// This function is only for empty list
if (head != NULL)
return head;
// Creating a node dynamically.
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp->data = data;
head = temp;
// Creating the link.
head->next = head;
return head;
}
struct Node* addBegin(struct Node* head, int data)
{
if (head == NULL)
return addToEmpty(head, data);
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = head->next;
head->next = temp;
return head;
}
/* function for traversing the list */
void traverse(struct Node* head)
{
struct Node* p;
// If list is empty, return.
if (head == NULL) {
cout << "List is empty." << endl;
return;
}
// Pointing to first Node of the list.
p = head;
// Traversing the list.
do {
cout << p->data << " ";
p = p->next;
} while (p != head);
}
/* Function to exchange first and last node*/
struct Node* exchangeNodes(struct Node* head)
{
// If list is of length less than 2
if (head == NULL || head->next == NULL) {
return head;
}
Node* tail = head;
// Find pointer to the last node
while (tail->next != head) {
tail = tail->next;
}
/* Exchange first and last nodes using
head and p */
// temporary variable to store
// head data
int temp = tail->data;
tail->data = head->data;
head->data = temp;
return head;
}
// Driven Program
int main()
{
int i;
struct Node* head = NULL;
head = addToEmpty(head, 6);
for (i = 5; i > 0; i--)
head = addBegin(head, i);
cout << "List Before: ";
traverse(head);
cout << endl;
cout << "List After: ";
head = exchangeNodes(head);
traverse(head);
return 0;
}
Java
// JAVA program to exchange first and
// last node in circular linked list
class GFG{
static class Node {
int data;
Node next;
};
static Node addToEmpty(Node head, int data)
{
// This function is only for empty list
if (head != null)
return head;
// Creating a node dynamically.
Node temp
= new Node();
// Assigning the data.
temp.data = data;
head = temp;
// Creating the link.
head.next = head;
return head;
}
static Node addBegin(Node head, int data)
{
if (head == null)
return addToEmpty(head, data);
Node temp
= new Node();
temp.data = data;
temp.next = head.next;
head.next = temp;
return head;
}
/* function for traversing the list */
static void traverse(Node head)
{
Node p;
// If list is empty, return.
if (head == null) {
System.out.print("List is empty." +"\n");
return;
}
// Pointing to first Node of the list.
p = head;
// Traversing the list.
do {
System.out.print(p.data+ " ");
p = p.next;
} while (p != head);
}
/* Function to exchange first and last node*/
static Node exchangeNodes(Node head)
{
// If list is of length less than 2
if (head == null || head.next == null) {
return head;
}
Node tail = head;
// Find pointer to the last node
while (tail.next != head) {
tail = tail.next;
}
/* Exchange first and last nodes using
head and p */
// temporary variable to store
// head data
int temp = tail.data;
tail.data = head.data;
head.data = temp;
return head;
}
// Driven Program
public static void main(String[] args)
{
int i;
Node head = null;
head = addToEmpty(head, 6);
for (i = 5; i > 0; i--)
head = addBegin(head, i);
System.out.print("List Before: ");
traverse(head);
System.out.println();
System.out.print("List After: ");
head = exchangeNodes(head);
traverse(head);
}
}
// This code is contributed by umadevi9616
Python3
# Python program to exchange first and
# last node in circular linked list class Node {
class Node:
def __init__(self):
self.data = 0
self.next = None
def addToEmpty(head, data):
# This function is only for empty list
if (head != None):
return head
# Creating a node dynamically.
temp = Node()
# Assigning the data.
temp.data = data
head = temp
# Creating the link.
head.next = head
return head
def addBegin(head, data):
if (head == None):
return addToEmpty(head, data)
temp = Node()
temp.data = data
temp.next = head.next
head.next = temp
return head
# function for traversing the list
def traverse(head):
# If list is empty, return.
if (head == None):
print("List is empty.")
return
# Pointing to first Node of the list.
p = head
# Traversing the list.
while (True):
print(p.data, end=" ")
p = p.next
if(p == head):
break
# Function to exchange first and last node
def exchangeNodes(head):
# If list is of length less than 2
if (head == None or head.next == None):
return head
tail = head
# Find pointer to the last node
while (tail.next != head):
tail = tail.next
# Exchange first and last nodes using head and p
# temporary variable to store
# head data
temp = tail.data
tail.data = head.data
head.data = temp
return head
# Driven Program
head = None
head = addToEmpty(head, 6)
for i in range(5, 0, -1):
head = addBegin(head, i)
print("List Before: ")
traverse(head)
print("")
print("List After: ")
head = exchangeNodes(head)
traverse(head)
# This code is contributed by Saurabh Jaiswal
C#
// C# program to exchange first and
// last node in circular linked list
using System;
public class GFG {
public class Node {
public int data;
public Node next;
};
static Node addToEmpty(Node head, int data) {
// This function is only for empty list
if (head != null)
return head;
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
head = temp;
// Creating the link.
head.next = head;
return head;
}
static Node addBegin(Node head, int data) {
if (head == null)
return addToEmpty(head, data);
Node temp = new Node();
temp.data = data;
temp.next = head.next;
head.next = temp;
return head;
}
/* function for traversing the list */
static void traverse(Node head) {
Node p;
// If list is empty, return.
if (head == null) {
Console.Write("List is empty." + "\n");
return;
}
// Pointing to first Node of the list.
p = head;
// Traversing the list.
do {
Console.Write(p.data + " ");
p = p.next;
} while (p != head);
}
/* Function to exchange first and last node */
static Node exchangeNodes(Node head) {
// If list is of length less than 2
if (head == null || head.next == null) {
return head;
}
Node tail = head;
// Find pointer to the last node
while (tail.next != head) {
tail = tail.next;
}
/*
* Exchange first and last nodes using head and p
*/
// temporary variable to store
// head data
int temp = tail.data;
tail.data = head.data;
head.data = temp;
return head;
}
// Driven Program
public static void Main(String[] args) {
int i;
Node head = null;
head = addToEmpty(head, 6);
for (i = 5; i > 0; i--)
head = addBegin(head, i);
Console.Write("List Before: ");
traverse(head);
Console.WriteLine();
Console.Write("List After: ");
head = exchangeNodes(head);
traverse(head);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program to exchange first and
// last node in circular linked list class Node {
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
function addToEmpty(head , data) {
// This function is only for empty list
if (head != null)
return head;
// Creating a node dynamically.
var temp = new Node();
// Assigning the data.
temp.data = data;
head = temp;
// Creating the link.
head.next = head;
return head;
}
function addBegin(head , data) {
if (head == null)
return addToEmpty(head, data);
var temp = new Node();
temp.data = data;
temp.next = head.next;
head.next = temp;
return head;
}
/* function for traversing the list */
function traverse(head) {
var p;
// If list is empty, return.
if (head == null) {
document.write("List is empty." + "\n");
return;
}
// Pointing to first Node of the list.
p = head;
// Traversing the list.
do {
document.write(p.data + " ");
p = p.next;
} while (p != head);
}
/* Function to exchange first and last node */
function exchangeNodes(head) {
// If list is of length less than 2
if (head == null || head.next == null) {
return head;
}
var tail = head;
// Find pointer to the last node
while (tail.next != head) {
tail = tail.next;
}
/*
* Exchange first and last nodes using head and p
*/
// temporary variable to store
// head data
var temp = tail.data;
tail.data = head.data;
head.data = temp;
return head;
}
// Driven Program
var i;
var head = null;
head = addToEmpty(head, 6);
for (i = 5; i > 0; i--)
head = addBegin(head, i);
document.write("List Before: <br/>");
traverse(head);
document.write("<br/>");
document.write("List After: <br/>");
head = exchangeNodes(head);
traverse(head);
// This code is contributed by umadevi9616
</script>
Producción
List Before: 6 1 2 3 4 5 List After: 5 1 2 3 4 6
Complejidad de tiempo: O(n) , ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1) , ya que no estamos utilizando ningún espacio adicional.
Este artículo es una contribución de R_Raj . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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