Rotate List

                                            
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) return head;
        
        int len = 1;
        ListNode *tail = head;
        while (tail->next) {
            len++;
            tail = tail->next;
        }
        
        k = k % len;
        if (k == 0) return head;
        
        ListNode *newTail = head;
        for (int i = 0; i < len - k - 1; i++) {
            newTail = newTail->next;
        }
        
        ListNode *newHead = newTail->next;
        newTail->next = nullptr;
        tail->next = head;
        
        return newHead;
    }
};

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        
        int length = 1;
        ListNode curr = head;
        while (curr.next != null) {
            length++;
            curr = curr.next;
        }
        curr.next = head;
        
        k = k % length;
        for (int i = 0; i < length - k; i++) {
            curr = curr.next;
        }
        
        ListNode newHead = curr.next;
        curr.next = null;
        
        return newHead;
    }
}

                                            
class Solution(object):
    def rotateRight(self, head, k):
        if not head or not head.next or k == 0:
            return head
        
        # calculate the length of the linked list
        length = 1
        curr = head
        while curr.next:
            curr = curr.next
            length += 1
        
        # connect the last node with the head to make it a circular linked list
        curr.next = head
        
        # find kth node from the end (length - k % length) and set it as the new head
        new_head_index = length - k % length - 1
        new_head = head
        for _ in range(new_head_index):
            new_head = new_head.next
        
        # update the new head and break the circular linked list
        head = new_head.next
        new_head.next = None
        
        return head

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (head == NULL || head->next == NULL || k == 0) {
        return head;
    }
    
    int length = 1;
    struct ListNode* current = head;
    while (current->next != NULL) {
        current = current->next;
        length++;
    }
    
    current->next = head;
    k = k % length;
    
    for (int i = 0; i < length - k; i++) {
        current = current->next;
    }
    
    head = current->next;
    current->next = NULL;
    
    return head;
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        
        // Get the length of the list
        int length = 1;
        ListNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
            length++;
        }
        
        k = k % length;
        if (k == 0) {
            return head;
        }
        
        // Connect the last node to the head to create a loop
        temp.next = head;
        
        // Find the new head and break the loop
        k = length - k;
        for (int i = 0; i < k; i++) {
            temp = temp.next;
        }
        ListNode newHead = temp.next;
        temp.next = null;
        
        return newHead;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if (!head || k === 0) {
        return head;
    }
    
    let current = head;
    let length = 1;
    while (current.next) {
        current = current.next;
        length++;
    }
    
    current.next = head;
    
    let newTail = head;
    for (let i = 0; i < length - k % length - 1; i++) {
        newTail = newTail.next;
    }
    
    let newHead = newTail.next;
    newTail.next = null;
    
    return newHead;
};

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 */
function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (!head || !head.next || k === 0) {
        return head;
    }
    
    let length = 1;
    let tail = head;
    while (tail.next) {
        tail = tail.next;
        length++;
    }
    
    k = k % length;
    if (k === 0) {
        return head;
    }
    
    let newTail = head;
    for (let i = 1; i < length - k; i++) {
        newTail = newTail.next;
    }
    
    const newHead = newTail.next;
    newTail.next = null;
    tail.next = head;
    
    return newHead;
}

                                            
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 */
class Solution {
    /**
     * @param ListNode $head
     * @param Integer $k
     * @return ListNode
     */
    function rotateRight($head, $k) {
        if (!$head || !$head->next || $k === 0) return $head;
        
        $length = 1;
        $tail = $head;
        while ($tail->next) {
            $tail = $tail->next;
            $length++;
        }
        
        $k = $k % $length;
        if ($k === 0) return $head;
        
        $newTail = $head;
        for ($i = 0; $i < $length - $k - 1; $i++) {
            $newTail = $newTail->next;
        }
        
        $newHead = $newTail->next;
        $newTail->next = null;
        $tail->next = $head;
        
        return $newHead;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val;
 *         self.next = next;
 *     }
 * }
 */
 
class Solution {
    func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
        if head == nil || k == 0 {
            return head
        }
        
        var length = 1
        var tail = head
        
        while tail?.next != nil {
            length += 1
            tail = tail?.next
        }
        
        let steps = length - k % length
        tail?.next = head
        
        var newTail = tail
        var newHead = head
        
        for _ in 0..<steps {
            newTail = newHead
            newHead = newHead?.next
        }
        
        newTail?.next = nil
        
        return newHead
    }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil || k == 0 {
        return head
    }
    
    cur := head
    length := 1
    for cur.Next != nil {
        cur = cur.Next
        length++
    }
    cur.Next = head
    
    k = k % length
    for i := 0; i < length-k; i++ {
        cur = cur.Next
    }
    
    newHead := cur.Next
    cur.Next = nil
    
    return newHead
}

                                            
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end

def rotate_right(head, k)
    return head if head.nil? || head.next.nil? || k == 0
    dummy = ListNode.new(0)
    dummy.next = head
    current = head
    length = 1
    
    while current.next
        current = current.next
        length += 1
    end
    
    k = k % length
    return head if k == 0
    
    fast = slow = head
    (1..k).each do
        fast = fast.next
    end
    
    while fast.next
        slow = slow.next
        fast = fast.next
    end
    
    new_head = slow.next
    slow.next = nil
    fast.next = head
    new_head
end

                                            
/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
    def rotateRight(head: ListNode, k: Int): ListNode = {
        if (head == null || head.next == null || k == 0) return head
        
        var length = 1
        var tail = head
        while (tail.next != null) {
            tail = tail.next
            length += 1
        }
        
        var newK = k % length
        if (newK == 0) return head
        
        var fast = head
        var slow = head
        for (_ <- 0 until newK) {
            fast = fast.next
        }
        
        while (fast.next != null) {
            fast = fast.next
            slow = slow.next
        }
        
        val newHead = slow.next
        slow.next = null
        fast.next = head
        
        newHead
    }
}

To solve this coding challenge, we need to rotate a given linked list to the right by

k

places, then return the head of the newly rotated list. Let's walk through the methodology for resolving this challenge.

# Explanation:

Edge Cases Handling : First, we need to handle the possible edge cases:

If the list is empty (
head

is
None

) or contains only one node (
head.next

is
None

), or if
k

is
0

, then the list remains unchanged.

Calculate the Length : We traverse the linked list to calculate its length. This helps in dealing with scenarios where
k

is larger than the length of the list.
Make Circular : To easily rotate the list, we connect the last node back to the
head

node, making the linked list circular.
Find New Head : Compute the new head position by using the formula
new_head_index = length - k % length

. This is because rotating
k

places to the right is the same as rotating
k % length

places to the right.
Break Circular Link : Traverse to the new head, update the
head

, and break the circular link to finalize the rotated list.

Detailed Steps in Pseudocode:

Edge Cases Handling :

                                            
IF head IS None OR head.next IS None OR k IS 0
RETURN head  # List remains unchanged

Calculate the Length of the List :

                                            
SET length TO 1
SET current_node TO head
WHILE current_node.next IS NOT None
current_node TO current_node.next
length TO length + 1

Make the List Circular :

                                            
SET current_node.next TO head  # Making the list circular

Find the New Head :

                                            
SET new_head_index TO length - k % length - 1
SET new_head TO head
FOR i FROM 0 TO new_head_index
new_head TO new_head.next

Break the Circular Link and Set New Head :

                                            
SET head TO new_head.next  # New head after rotation
SET new_head.next TO None  # Breaking the circular link
RETURN head

By breaking down the problem into these steps, we can systematically address each part of the process, ensuring that we handle edge cases, calculate necessary transformations, and adjust our linked list accordingly. Here's how the overall pseudocode would look:

                                            
# Function to rotate linked list to the right by k places
FUNCTION rotateRight(head, k)
    # Handling edge cases
    IF head IS None OR head.next IS None OR k IS 0
        RETURN head  # List remains unchanged
    
    # Calculate the length of the linked list
    SET length TO 1
    SET current_node TO head
    WHILE current_node.next IS NOT None
        current_node TO current_node.next
        length TO length + 1
    
    # Make the linked list circular
    SET current_node.next TO head
    
    # Find the new head's index after rotation
    SET new_head_index TO length - k % length - 1
    SET new_head TO head
    FOR i FROM 0 TO new_head_index
        new_head TO new_head.next

    # Set the new head and break the circular connection
    SET head TO new_head.next  # New head after rotation
    SET new_head.next TO None  # Breaking the circular link
    RETURN head

This pseudocode ensures that the linked list is rotated correctly according to the problem constraints and handles all edge cases effectively.