61-旋转链表

LeetCode 61. Rotate List

LeetCode-61

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]

method

连接成环，然后从尾部走len-k步，下一个节点就是新的头结点，因为k可能比len大，所以要模以len，所以是len-(k % len)

ListNode* rotateRight(ListNode* head, int k) {
    if (k == 0 || !head || !head->next) return head;
    int len = 1;
    ListNode *cur = head;
    while (cur->next) {
        len++;
        cur = cur->next;
    }
    int count = len - (k % len);  // 计算要走几步
    if (count == len) return head;
    cur->next = head;   // 连接成环
    while (count--) cur = cur->next;  // 移动len-k
    ListNode *node = cur->next;  // 新的头结点
    cur->next = nullptr;    // 要断开
    return node;
}