import java.util.*;

// Definition of singly linked list
class ListNode {
    int val;
    ListNode next;
    ListNode() {
        val = 0;
        next = null;
    }
    ListNode(int data1) {
        val = data1;
        next = null;
    }
    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

class Solution {
    // Function to rotate the list by k steps
    public ListNode rotateRight(ListNode head, int k) {
        // Base case: if list is empty or has only one node
        if (head == null || head.next == null)
            return head;

        // Perform rotation k times
        for (int i = 0; i < k; i++) {
            ListNode temp = head;
            // Find the second last node
            while (temp.next.next != null) temp = temp.next;
            // Get the last node
            ListNode end = temp.next;
            // Break the link between 
            // second last and last node
            temp.next = null;
            // Make the last node
            // as new head
            end.next = head;
            head = end;
        }
        return head;
    }
}

// Utility function to insert node at the end of the list
public static void insertNode(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    if (head == null) {
        head = newNode;
        return;
    }
    ListNode temp = head;
    while (temp.next != null) temp = temp.next;
    temp.next = newNode;
}

// Utility function to print list
public static void printList(ListNode head) {
    while (head != null) {
        System.out.print(head.val);
        if (head.next != null) System.out.print("->");
        head = head.next;
    }
    System.out.println();
}

public static void main(String[] args) {
    ListNode head = new ListNode(1);
    // Inserting nodes
    insertNode(head, 2);
    insertNode(head, 3);
    insertNode(head, 4);
    insertNode(head, 5);

    System.out.print("Original list: ");
    printList(head);

    int k = 2;
    Solution solution = new Solution();
    // Calling function for rotating right by k times
    ListNode newHead = solution.rotateRight(head, k);

    System.out.print("After " + k + " iterations: ");
    // List after rotating nodes
    printList(newHead);
}

# Definition of Single Linked List
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to rotate the list by k steps
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        # Base case: if list is empty or has only one node
        if not head or not head.next:
            return head

        # Perform rotation k times
        for _ in range(k):
            temp = head
            # Find the second last node
            while temp.next.next:
                temp = temp.next
            # Get the last node
            end = temp.next
            # Break the link between 
            # second last and last node
            temp.next = None
            # Make the last node 
            # as new head
            end.next = head
            head = end

        return head

# Utility function to insert node at end of list
def insert_node(head, val):
    new_node = ListNode(val)
    if not head:
        return new_node
    temp = head
    while temp.next:
        temp = temp.next
    temp.next = new_node
    return head

# Utility function to print list
def print_list(head):
    while head:
        print(head.val, end="->" if head.next else "")
        head = head.next
    print()

if __name__ == "__main__":
    head = ListNode(1)
    # Inserting nodes
    head = insert_node(head, 2)
    head = insert_node(head, 3)
    head = insert_node(head, 4)
    head = insert_node(head, 5)

    print("Original list: ", end="")
    print_list(head)

    k = 2
    solution = Solution()
    # Calling function for rotating right by k times
    new_head = solution.rotateRight(head, k)

    print(f"After {k} iterations: ", end="")
    # List after rotating nodes
    print_list(new_head)

// Definition of Single Linked List
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Function to rotate the list by k steps
    rotateRight(head, k) {
        // Base case: if list is empty or has only one node
        if (!head || !head.next) 
            return head;

        // Perform rotation k times
        for (let i = 0; i < k; i++) {
            let temp = head;
            // Find the second last node
            while (temp.next.next) temp = temp.next;
            // Get the last node
            let end = temp.next;
            // Break the link between 
            // second last and last node
            temp.next = null;
            // Make the last node 
            // as new head
            end.next = head;
            head = end;
        }
        return head;
    }
}

// Utility function to insert node at end of list
function insertNode(head, val) {
    let newNode = new ListNode(val);
    if (!head) {
        return newNode;
    }
    let temp = head;
    while (temp.next) temp = temp.next;
    temp.next = newNode;
    return head;
}

// Utility function to print list
function printList(head) {
    while (head) {
        process.stdout.write(head.val.toString());
        if (head.next) process.stdout.write("->");
        head = head.next;
    }
    console.log();
}

let head = new ListNode(1);
// Inserting nodes
head = insertNode(head, 2);
head = insertNode(head, 3);
head = insertNode(head, 4);
head = insertNode(head, 5);

console.log("Original list: ");
printList(head);

let k = 2;
let solution = new Solution();
// Calling function for rotating right by k times
let newHead = solution.rotateRight(head, k);

console.log("After " + k + " iterations: ");
// List after rotating nodes
printList(newHead);