Rotate a Linked List by k Places

medium linked list

Problem

Given a singly linked list and a non-negative integer k, rotate the list to the right by k positions. After rotation, the original tail's next becomes the original head, and the new head sits k places before the old tail.

Walk to the tail to count the length n; close the list into a cycle by setting tail.next = head; advance n − (k mod n) steps from the head to find the new tail; cut the cycle there.

Input1 → 2 → 3 → 4 → 5, k = 2

Output4 → 5 → 1 → 2 → 3

list (comma-separated)

def rotate_right(head, k):
    if not head or not head.next or k == 0: return head
    n = 1; tail = head
    while tail.next: tail = tail.next; n += 1
    k %= n
    if k == 0: return head
    tail.next = head
    new_tail = head
    for _ in range(n - k - 1): new_tail = new_tail.next
    new_head = new_tail.next
    new_tail.next = None
    return new_head

function rotateRight(head, k) {
  if (!head || !head.next || k === 0) return head;
  let n = 1, tail = head;
  while (tail.next) { tail = tail.next; n++; }
  k %= n;
  if (k === 0) return head;
  tail.next = head;
  let newTail = head;
  for (let i = 0; i < n - k - 1; i++) newTail = newTail.next;
  const newHead = newTail.next;
  newTail.next = null;
  return newHead;
}

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

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

Time: O(n) Space: O(1)