Rotate List

Rotate List

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

• The number of nodes in the list is in the range [0, 500].

• -100 <= Node.val <= 100

• 0 <= k <= 2 * 109

Solutions

🧠 Cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    //O(n)solution with circular list
    ListNode* rotateRight(ListNode* head, int k)
    {
        if(!head)
            return head;

        //find list length and save tail
        size_t length = 0;
        ListNode *tail = nullptr;
        for(ListNode *counter = head; counter; ++length, counter = counter->next)
            if(!counter->next)
                tail = counter;

        //make list circular
        tail->next = head;

        //module k
        k = k % length;

        //we will move k last element to front
        //length - k element will be a new tail
        //length - k + 1 element will be a new head

        //find new tail:
        tail = head;
        for(int i = 0; i < length - k - 1; ++i, tail = tail->next);

        head = tail->next;
        tail->next = nullptr;

        return head;
    }
};