DeepSeek LeetCode 61. 旋转链表 C++实现

以下是 LeetCode 61. 旋转链表的 C++ 实现，包含详细注释。思路是先计算链表长度，连成环，再根据旋转步数确定新的头节点并断开环。

/** * 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) {} * }; */classSolution{public:ListNode*rotateRight(ListNode*head,intk){// 空链表、单节点或无需旋转的情况if(!head||!head->next||k==0)returnhead;// 1. 计算链表长度，并找到尾节点intn=1;ListNode*tail=head;while(tail->next){tail=tail->next;n++;}// 2. 将链表首尾相连，形成环tail->next=head;// 3. 实际需要移动的步数（取模，避免重复旋转）k=k%n;// 4. 找到新的尾节点：原头节点向前走 n - k - 1 步// （因为新头是原头向右移动 n-k 个位置，即新尾是原头向左移动 k 个位置）ListNode*newTail=head;for(inti=1;i<n-k;i++){newTail=newTail->next;}// 5. 断开环，得到新链表ListNode*newHead=newTail->next;newTail->next=nullptr;returnnewHead;}};

复杂度分析：

· 时间复杂度：O(n)，其中 n 是链表长度。需要遍历链表两次（一次求长度，一次找新尾），但总体仍是线性。
· 空间复杂度：O(1)，只使用了常数个额外指针。

关键点：

· 将链表连成环后，旋转操作等价于在正确位置断开环。
· 使用取模避免 k 大于链表长度时的无效遍历。
· 注意处理边界情况（空链表、单节点、k=0）。