描述

在一个单链表中，在第k个位置向右旋转单链表，k是一个非负值。

输入：

​ 1->2->3->4->5->nullptr， k=2

输出

​ 4->5->1->2->3->nullptr

分析

遍历链表，计算出链表的长度，将链表的尾结点连接到头节点形成一个环链表，再往后遍历len-k个节点，从此将链表断开即可。需要兼容k超出链表长度时的情况。

实现

ListNode *rotateList(ListNode *head, int k)
{
    int len = 1;
    
    // 计算长度
    ListNode *cur = head;
    while (cur->next) {
        ++len;
        cur = cur->next;
    }
    
    // 兼容k
    k = len - k%len;
    
    //形成环链表
    cur->next = head;
    
    // 再向前走k个节点
    for(int i=0; i<k; i++) {
        cur = cur->next;
    }
    head = cur->next;
    cur->next = nullptr;
    
    return head;
}

时间复杂度O(n)，空间复杂度为O(1)。