SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

When rotating a linked list to the right by k places, we need to move the last k nodes to the front of the list. If the list has n nodes, rotating by k is equivalent to rotating by k % n (because rotating by n brings the list back to its original form). The challenge lies in finding the new head and tail of the rotated list and correctly re-linking the nodes.

Approach

1. Edge Case Handling: First, check if the list is empty or contains only one node, or if k is zero. In these cases, return the original list as it is.

2. Calculate Length: Traverse the list to calculate its length (n).

3. Adjust k: Compute k % n to handle cases where k is larger than the list length.

4. Find the New Tail: Identify the new tail of the rotated list. This node will be at position n - k - 1 from the start of the list.

5. Re-link the List:

   • The new head will be the node after the new tail.
   • Set the next pointer of the new tail to null.
   • Traverse to the end of the original list and link it to the original head.

6. Return the New Head: Finally, return the new head of the list.

Complexity

Time Complexity:

O(n) where n is the number of nodes in the list. This is because we need to traverse the list twice: once to calculate the length and once to re-link the nodes.

Space Complexity:

O(1). The algorithm uses a constant amount of extra space.

Code

C++

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return head;

        int n = length(head);
        if (k % n == 0) return head;

        k = n > k ? k : k % n;

        ListNode* node = head;
        for (int i = 0; i < n - k - 1; ++i) {
            node = node->next;
        }

        ListNode* res = node->next;
        node->next = nullptr;

        ListNode* tail = res;
        while (tail->next) {
            tail = tail->next;
        }

        tail->next = head;
        return res;
    }

private:
    int length(ListNode* node) {
        int n = 0;
        while (node) {
            node = node->next;
            n++;
        }
        return n;
    }
};

Python

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return head

        n = self.length(head)
        if k % n == 0:
            return head

        k = k % n

        node = head
        for _ in range(n - k - 1):
            node = node.next

        res = node.next
        node.next = None

        tail = res
        while tail.next:
            tail = tail.next

        tail.next = head
        return res

    def length(self, node: Optional[ListNode]) -> int:
        n = 0
        while node:
            node = node.next
            n += 1
        return n

Java

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return head;

        int n = length(head);
        if (k % n == 0) return head;

        k = n > k ? k : k % n;

        ListNode node = head;
        for (int i = 0; i < n - k - 1; ++i) {
            node = node.next;
        }

        ListNode res = node.next;
        node.next = null;

        ListNode tail = res;
        while (tail.next != null) {
            tail = tail.next;
        }

        tail.next = head;
        return res;
    }

    private int length(ListNode node) {
        int n = 0;
        while (node != null) {
            node = node.next;
            n++;
        }
        return n;
    }
}

JavaScript

var rotateRight = function (head, k) {
    let n = length(head)

    if (k % n === 0 || !head) return head

    let node = head
    k = n > k ? k : k % n

    while (n - k - 1) {
        node = node.next
        k++
    }
    res = tail = node.next

    node.next = null
    while (tail.next) {
        tail = tail.next
    }
    tail.next = head
    return res
};

var length = function (node) {
    let n = 0;

    while (node) {
        node = node.next
        n++
    }

    return n
}