61. Rotate List

Posted on Edited on In

61. Rotate List

Description

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

Example 1:

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

Example 2:

1
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 * 10^9

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) {
            return head;
        }
        int n = 1;
        ListNode* cur = head;
        while (cur->next) {
            n++;
            cur = cur->next;
        }
        ListNode* old_tail = cur;
        k = k % n;
        if (!k) {
            return head;
        }
        k = n - k - 1;
        cur = head;
        while (k) {
            k--;
            cur = cur->next;
        }
        ListNode* newHead = cur->next;
        cur->next = nullptr;
        old_tail->next = head;
        return newHead;
    }
};