61.旋转链表：算总长——算新头

【LetMeFly】61.旋转链表：算总长——算新头

力扣题目链接：https://leetcode.cn/problems/rotate-list/

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

 

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

 

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

解题方法：两次遍历

第一次遍历一遍链表，计算出链表长度$n$，将链表尾节点指向头节点，形成循环链表。

之后将$k\mod n$，将链表右移$k$次相当于令倒数第$k$个节点变成新链表的头部，即将正着数第$n-k$个节点变成新头。

让新头节点的上一个节点next指向空，返回新头节点就好了。

注意链表可能为空，记得避免空指针情况发生。

• 时间复杂度$O(len(listnode))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-05-05 11:49:41
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) {
            return nullptr;
        }
        
        int n = 1;
        ListNode* p = head;
        while (p->next) {
            n++;
            p = p->next;
        }
        p->next = head;
        k %= n;
        k = n - k;

        p = head;
        for (int i = 1; i < k; i++) {
            p = p->next;
        }
        ListNode* ans = p->next;
        p->next = nullptr;
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源