用c+编写一个程序,给你一个链表的头节点head,旋转链表,将链表每个节点向右移动 k个位置,返回 移动后的链表。 示例: 输入:1→2→3→4→5,k=2 输出:4→5→1→2→3
时间: 2024-09-24 11:10:18 浏览: 27
在C++中,你可以通过创建一个辅助函数来实现链表的右旋操作。这里是一个简单的步骤:
首先,需要定义链表节点结构体:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
```
然后可以创建一个函数来完成链表的旋转:
```cpp
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next || k == 0) {
return head; // 如果链表为空或者k为0,直接返回原链表
}
// 找到链表的实际长度(包括k次旋转)
int len = 1;
ListNode* tail = head;
while (tail->next) {
tail = tail->next;
len++;
}
k %= len; // 取模运算,使得k在实际长度范围内
// 分离出前k个节点
tail->next = head;
ListNode* newHead = nullptr;
for (int i = 0; i < len - k; i++) {
newHead = head->next;
head->next = head->next->next;
}
head = newHead; // 新的头部就是原k个节点后的部分
return head;
}
```
这个函数首先检查特殊情况,然后计算链表的实际长度,并通过迭代找到新的头部。最后,它调整节点指针以实现链表的旋转。
下面是一个完整的示例程序:
```cpp
#include <iostream>
// ... (上面的链表节点和旋转函数)
int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
int k = 2;
ListNode* rotatedHead = rotateRight(head, k);
// 输出旋转后的链表
while (rotatedHead) {
std::cout << rotatedHead->val << " ";
rotatedHead = rotatedHead->next;
}
std::cout << std::endl;
// 释放内存
delete rotatedHead;
delete head;
return 0;
}