有n个整数,使前面各数顺序向后移m个位置,最后m个数变成前面m个数,见图。写一函数:实现以上功能,在主函数中输入n个数和输出调整后的n个数。 y用链表实现 链表创建用函数写
时间: 2024-05-09 12:14:48 浏览: 78
好的,我理解了你的问题。我可以为你提供一个C++的实现,使用链表来实现这个功能。
首先,我们需要定义一个链表节点的结构体,包含一个整数值和一个指向下一个节点的指针:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
```
接下来,我们需要实现一个函数来创建链表。这个函数将依次读入n个整数,然后将它们按顺序存储在链表中:
```cpp
ListNode* createList(int n) {
ListNode* head = nullptr;
ListNode* cur = nullptr;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
if (!head) {
head = new ListNode(x);
cur = head;
} else {
cur->next = new ListNode(x);
cur = cur->next;
}
}
return head;
}
```
接下来,我们需要实现一个函数来实现链表向后移动m个位置的功能。我们可以先将链表的尾部连接到头部,然后从头开始遍历链表,找到新的头节点和尾节点,最后将尾节点的next指针置为空:
```cpp
ListNode* adjustList(ListNode* head, int m) {
if (!head || !head->next || m == 0) {
return head; // 链表为空或只有一个节点或m为0,直接返回
}
// 遍历到链表尾部,同时记录链表长度
int len = 1;
ListNode* tail = head;
while (tail->next) {
len++;
tail = tail->next;
}
// 将链表尾部连接到头部
tail->next = head;
// 找到新的头节点和尾节点
int k = len - m % len;
ListNode* newTail = tail;
while (k--) {
newTail = newTail->next;
}
ListNode* newHead = newTail->next;
// 断开链表
newTail->next = nullptr;
return newHead;
}
```
最后,我们在主函数中调用上面的函数,输入n个整数,并输出调整后的n个整数:
```cpp
int main() {
int n, m;
std::cin >> n >> m;
ListNode* head = createList(n);
head = adjustList(head, m);
while (head) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << std::endl;
return 0;
}
```
注意,这个函数的时间复杂度为O(n),空间复杂度为O(1),是一个比较高效的算法。
阅读全文