Dada una lista enlazada de n Nodes que primero se ordena y luego se rota por k elementos. Encuentre el valor de k.
C++
// Program for count number of rotations in
// sorted linked list.
#include <bits/stdc++.h>
using namespace std;
/* Linked list node */
struct Node {
int data;
struct Node* next;
};
// Function that count number of
// rotation in singly linked list.
int countRotation(struct Node* head)
{
// declare count variable and assign it 1.
int count = 0;
// declare a min variable and assign to
// data of head node.
int min = head->data;
// check that while head not equal to NULL.
while (head != NULL) {
// if min value is greater then head->data
// then it breaks the while loop and
// return the value of count.
if (min > head->data)
break;
count++;
// head assign the next value of head.
head = head->next;
}
return count;
}
// Function to push element in linked list.
void push(struct Node** head, int data)
{
// Allocate dynamic memory for newNode.
struct Node* newNode = new Node;
// Assign the data into newNode.
newNode->data = data;
// newNode->next assign the address of
// head node.
newNode->next = (*head);
// newNode become the headNode.
(*head) = newNode;
}
// Display linked list.
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
// Driver functions
int main()
{
// Create a node and initialize with NULL
struct Node* head = NULL;
// push() insert node in linked list.
// 15 -> 18 -> 5 -> 8 -> 11 -> 12
push(&head, 12);
push(&head, 11);
push(&head, 8);
push(&head, 5);
push(&head, 18);
push(&head, 15);
printList(head);
cout << endl;
cout << "Linked list rotated elements: ";
// Function call countRotation()
cout << countRotation(head) << endl;
return 0;
}
Java
// Program for count number of rotations in
// sorted linked list.
import java.util.*;
class GFG
{
/* Linked list node */
static class Node {
int data;
Node next;
};
// Function that count number of
// rotation in singly linked list.
static int countRotation(Node head)
{
// declare count variable and assign it 1.
int count = 0;
// declare a min variable and assign to
// data of head node.
int min = head.data;
// check that while head not equal to null.
while (head != null) {
// if min value is greater then head.data
// then it breaks the while loop and
// return the value of count.
if (min > head.data)
break;
count++;
// head assign the next value of head.
head = head.next;
}
return count;
}
// Function to push element in linked list.
static Node push(Node head, int data)
{
// Allocate dynamic memory for newNode.
Node newNode = new Node();
// Assign the data into newNode.
newNode.data = data;
// newNode.next assign the address of
// head node.
newNode.next = (head);
// newNode become the headNode.
(head) = newNode;
return head;
}
// Display linked list.
static void printList(Node node)
{
while (node != null) {
System.out.printf("%d ", node.data);
node = node.next;
}
}
// Driver functions
public static void main(String[] args)
{
// Create a node and initialize with null
Node head = null;
// push() insert node in linked list.
// 15.18.5.8.11.12
head = push(head, 12);
head = push(head, 11);
head = push(head, 8);
head = push(head, 5);
head = push(head, 18);
head = push(head, 15);
printList(head);
System.out.println();
System.out.print("Linked list rotated elements: ");
// Function call countRotation()
System.out.print(countRotation(head) +"\n");
}
}
// This code contributed by gauravrajput1
Python3
# Program for count number of rotations in
# sorted linked list.
# Linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function that count number of
# rotation in singly linked list.
def countRotation(head):
# Declare count variable and assign it 1.
count = 0
# Declare a min variable and assign to
# data of head node.
min = head.data
# Check that while head not equal to None.
while (head != None):
# If min value is greater then head->data
# then it breaks the while loop and
# return the value of count.
if (min > head.data):
break
count += 1
# head assign the next value of head.
head = head.next
return count
# Function to push element in linked list.
def push(head, data):
# Allocate dynamic memory for newNode.
newNode = Node(data)
# Assign the data into newNode.
newNode.data = data
# newNode->next assign the address of
# head node.
newNode.next = (head)
# newNode become the headNode.
(head) = newNode
return head
# Display linked list.
def printList(node):
while (node != None):
print(node.data, end = ' ')
node = node.next
# Driver code
if __name__=='__main__':
# Create a node and initialize with None
head = None
# push() insert node in linked list.
# 15 -> 18 -> 5 -> 8 -> 11 -> 12
head = push(head, 12)
head = push(head, 11)
head = push(head, 8)
head = push(head, 5)
head = push(head, 18)
head = push(head, 15)
printList(head);
print()
print("Linked list rotated elements: ",
end = '')
# Function call countRotation()
print(countRotation(head))
# This code is contributed by rutvik_56
C#
// Program for count number of rotations in
// sorted linked list.
using System;
class LinkedList{
// Head of linked list
Node head;
// Linked list node
class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
int countRotation()
{
// declare count variable and assign it 1.
int count = 0;
// declare a min variable and assign to
// data of head node.
int min = head.data;
// check that while head not equal to NULL.
while (head != null) {
// if min value is greater then head->data
// then it breaks the while loop and
// return the value of count.
if (min > head.data)
break;
count++;
// head assign the next value of head.
head = head.next;
}
return count;
}
// Inserts a new Node at front of the list.
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
// Function that count number of
// rotation in singly linked list.
public void printList()
{
Node tnode = head;
while (tnode != null)
{
Console.Write(tnode.data + "->");
tnode = tnode.next;
}
Console.WriteLine("NULL");
}
// Driver code
static public void Main()
{
LinkedList llist = new LinkedList();
llist.push(12);
llist.push(11);
llist.push(8);
llist.push(5);
llist.push(18);
llist.push(15);
llist.printList();
Console.Write("Linked list rotated elements: ");
Console.WriteLine(llist.countRotation());
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
// Program for count number of rotations in
// sorted linked list.
/* Linked list node */
class Node
{
constructor()
{
this.data=0;
this.next=null;
}
}
// Function that count number of
// rotation in singly linked list.
function countRotation(head)
{
// declare count variable and assign it 1.
let count = 0;
// declare a min variable and assign to
// data of head node.
let min = head.data;
// check that while head not equal to null.
while (head != null) {
// if min value is greater then head.data
// then it breaks the while loop and
// return the value of count.
if (min > head.data)
break;
count++;
// head assign the next value of head.
head = head.next;
}
return count;
}
// Function to push element in linked list.
function push(head,data)
{
// Allocate dynamic memory for newNode.
let newNode = new Node();
// Assign the data into newNode.
newNode.data = data;
// newNode.next assign the address of
// head node.
newNode.next = (head);
// newNode become the headNode.
(head) = newNode;
return head;
}
// Display linked list.
function printList(node)
{
while (node != null) {
document.write(node.data+" ");
node = node.next;
}
}
// Driver functions
// Create a node and initialize with null
let head = null;
// push() insert node in linked list.
// 15.18.5.8.11.12
head = push(head, 12);
head = push(head, 11);
head = push(head, 8);
head = push(head, 5);
head = push(head, 18);
head = push(head, 15);
printList(head);
document.write("<br>");
document.write("Linked list rotated elements: ");
// Function call countRotation()
document.write(countRotation(head) +"<br>");
// This code is contributed by unknown2108
</script>
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