Invertir una lista enlazada circular

Dada una lista enlazada circular de tamaño n . El problema es invertir la lista enlazada circular dada cambiando los enlaces entre los Nodes.
Ejemplos: 

APORTE: 
 

PRODUCCIÓN: 
 

Enfoque: El enfoque es el mismo que se sigue al invertir una lista de enlaces simples . Solo que aquí tenemos que hacer un ajuste más vinculando el último Node de la lista invertida al primer Node.

Implementación:

// C++ implementation to reverse
// a circular linked list
#include <bits/stdc++.h>
 
using namespace std;
 
// Linked list node
struct Node {
    int data;
    Node* next;
};
 
// function to get a new node
Node* getNode(int data)
{
    // allocate memory for node
    Node* newNode = new Node;
 
    // put in the data
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
// Function to reverse the circular linked list
void reverse(Node** head_ref)
{
    // if list is empty
    if (*head_ref == NULL)
        return;
 
    // reverse procedure same as reversing a
    // singly linked list
    Node* prev = NULL;
    Node* current = *head_ref;
    Node* next;
    do {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    } while (current != (*head_ref));
 
    // adjusting the links so as to make the
    // last node point to the first node
    (*head_ref)->next = prev;
    *head_ref = prev;
}
 
// Function to print circular linked list
void printList(Node* head)
{
    if (head == NULL)
        return;
 
    Node* temp = head;
    do {
        cout << temp->data << " ";
        temp = temp->next;
    } while (temp != head);
}
 
// Driver program to test above
int main()
{
    // Create a circular linked list
    // 1->2->3->4->1
    Node* head = getNode(1);
    head->next = getNode(2);
    head->next->next = getNode(3);
    head->next->next->next = getNode(4);
    head->next->next->next->next = head;
 
    cout << "Given circular linked list: ";
    printList(head);
 
    reverse(&head);
 
    cout << "\nReversed circular linked list: ";
    printList(head);
 
    return 0;
}

// Java implementation to reverse
// a circular linked list
class GFG
{
 
// Linked list node
static class Node
{
    int data;
    Node next;
};
 
// function to get a new node
static Node getNode(int data)
{
    // allocate memory for node
    Node newNode = new Node();
 
    // put in the data
    newNode.data = data;
    newNode.next = null;
    return newNode;
}
 
// Function to reverse the circular linked list
static Node reverse(Node head_ref)
{
    // if list is empty
    if (head_ref == null)
        return null;
 
    // reverse procedure same as reversing a
    // singly linked list
    Node prev = null;
    Node current = head_ref;
    Node next;
    do
    {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    } while (current != (head_ref));
 
    // adjusting the links so as to make the
    // last node point to the first node
    (head_ref).next = prev;
    head_ref = prev;
    return head_ref;
}
 
// Function to print circular linked list
static void printList(Node head)
{
    if (head == null)
        return;
 
    Node temp = head;
    do
    {
        System.out.print( temp.data + " ");
        temp = temp.next;
    } while (temp != head);
}
 
// Driver code
public static void main(String args[])
{
    // Create a circular linked list
    // 1.2.3.4.1
    Node head = getNode(1);
    head.next = getNode(2);
    head.next.next = getNode(3);
    head.next.next.next = getNode(4);
    head.next.next.next.next = head;
 
    System.out.print("Given circular linked list: ");
    printList(head);
 
    head = reverse(head);
 
    System.out.print("\nReversed circular linked list: ");
    printList(head);
 
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation to reverse
# a circular linked list
import math
 
# Linked list node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# function to get a new node
def getNode(data):
     
    # allocate memory for node
    newNode = Node(data)
 
    # put in the data
    newNode.data = data
    newNode.next = None
    return newNode
 
# Function to reverse the
# circular linked list
def reverse(head_ref):
     
    # if list is empty
    if (head_ref == None):
        return None
 
    # reverse procedure same as
    # reversing a singly linked list
    prev = None
    current = head_ref
     
    next = current.next
    current.next = prev
    prev = current
    current = next
    while (current != head_ref):
        next = current.next
        current.next = prev
        prev = current
        current = next
 
    # adjusting the links so as to make the
    # last node point to the first node
    head_ref.next = prev
    head_ref = prev
    return head_ref
 
# Function to print circular linked list
def printList(head):
    if (head == None):
        return
 
    temp = head
     
    print(temp.data, end = " ")
    temp = temp.next
    while (temp != head):
        print(temp.data, end = " ")
        temp = temp.next
 
# Driver Code
if __name__=='__main__':
     
    # Create a circular linked list
    # 1.2.3.4.1
    head = getNode(1)
    head.next = getNode(2)
    head.next.next = getNode(3)
    head.next.next.next = getNode(4)
    head.next.next.next.next = head
 
    print("Given circular linked list: ",
                                end = "")
    printList(head)
 
    head = reverse(head)
 
    print("\nReversed circular linked list: ",
                                     end = "")
    printList(head)
 
# This code is contributed by Srathore

// C# implementation to reverse
// a circular linked list
using System;
 
class GFG
{
 
    // Linked list node
    public class Node
    {
        public int data;
        public Node next;
    };
     
    // function to get a new node
    static Node getNode(int data)
    {
        // allocate memory for node
        Node newNode = new Node();
     
        // put in the data
        newNode.data = data;
        newNode.next = null;
        return newNode;
    }
     
    // Function to reverse the circular linked list
    static Node reverse(Node head_ref)
    {
        // if list is empty
        if (head_ref == null)
            return null;
     
        // reverse procedure same as reversing a
        // singly linked list
        Node prev = null;
        Node current = head_ref;
        Node next;
        do
        {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        } while (current != (head_ref));
     
        // adjusting the links so as to make the
        // last node point to the first node
        (head_ref).next = prev;
        head_ref = prev;
        return head_ref;
    }
     
    // Function to print circular linked list
    static void printList(Node head)
    {
        if (head == null)
            return;
     
        Node temp = head;
        do
        {
            Console.Write( temp.data + " ");
            temp = temp.next;
        } while (temp != head);
    }
     
    // Driver code
    public static void Main(String []args)
    {
        // Create a circular linked list
        // 1.2.3.4.1
        Node head = getNode(1);
        head.next = getNode(2);
        head.next.next = getNode(3);
        head.next.next.next = getNode(4);
        head.next.next.next.next = head;
     
        Console.Write("Given circular linked list: ");
        printList(head);
     
        head = reverse(head);
     
        Console.Write("\nReversed circular linked list: ");
        printList(head);
     
    }
}
 
// This code contributed by Rajput-Ji

<script>
 
      // JavaScript implementation to reverse
      // a circular linked list
      // Linked list node
      class Node {
        constructor() {
          this.data = 0;
          this.next = null;
        }
      }
 
      // function to get a new node
      function getNode(data) {
        // allocate memory for node
        var newNode = new Node();
 
        // put in the data
        newNode.data = data;
        newNode.next = null;
        return newNode;
      }
 
      // Function to reverse the circular linked list
      function reverse(head_ref) {
        // if list is empty
        if (head_ref == null) return null;
 
        // reverse procedure same as reversing a
        // singly linked list
        var prev = null;
        var current = head_ref;
        var next;
        do {
          next = current.next;
          current.next = prev;
          prev = current;
          current = next;
        } while (current != head_ref);
 
        // adjusting the links so as to make the
        // last node point to the first node
        head_ref.next = prev;
        head_ref = prev;
        return head_ref;
      }
 
      // Function to print circular linked list
      function printList(head) {
        if (head == null) return;
 
        var temp = head;
        do {
          document.write(temp.data + " ");
          temp = temp.next;
        } while (temp != head);
      }
 
      // Driver code
      // Create a circular linked list
      // 1.2.3.4.1
      var head = getNode(1);
      head.next = getNode(2);
      head.next.next = getNode(3);
      head.next.next.next = getNode(4);
      head.next.next.next.next = head;
 
      document.write("Given circular linked list: ");
      printList(head);
 
      head = reverse(head);
 
      document.write("<br>Reversed circular linked list: ");
      printList(head);
       
</script>

Given circular linked list: 1 2 3 4 
Reversed circular linked list: 4 3 2 1 

Complejidad de tiempo: O(n)

Este artículo es una contribución de Ayush Jauhari . 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.