于是,在本题中,你需要实现一个单链表 ,支持以下操作: 1.在单链表第 i 个数后面插入一个数 x 2.删除单链表第 i 个数 3.将单链表的奇偶位相互交换,若单链表长度为奇数,则剩下的最后一个元素无需交换。 4.将单链表前 i 个数整体往后移动 x 位。 5.输出单链表第 i 个数 6.输出整个单链表,使用空格隔开 另外,在程序开始时,请先读入一个大小为n 的数组对单链表进行初始化。 请通过动态申请空间的方式完成单链表。在程序结束后,你应当释放所有动态申请的内存。用C++语言完成 输入格式 第一行一个自然数 n ,代表初始化数组大小。 第二行 n 个整数,代表初始化数组。 第三行一个自然数 m ,代表操作数。 接下来 m 行每行第一个数为 op ,表示操作类型。 op=1,执行操作1,接下来读入两个整数 op=2,执行操作2,接下来读入一个整数 op=3,执行操作3 op=4,执行操作4,接下来读入两个整数 op=5,执行操作5,接下来读入一个整数 op=6,执行操作6 输出格式 对于每个操作5,操作6,一行输出操作的答案。(注意对于每一个操作,输出后需要换行)
时间: 2024-03-07 20:50:40 浏览: 64
我了解了你的问题,这是一个关于单链表操作的问题。这里给出一个C++的实现代码,你可以参考一下:
```cpp
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class MyLinkedList {
public:
/** Initialize your data structure here. */
MyLinkedList() {
dummyHead = new ListNode(-1);
size = 0;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode* cur = dummyHead->next;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
return cur->val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = dummyHead->next;
dummyHead->next = newNode;
size++;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
ListNode* newNode = new ListNode(val);
ListNode* cur = dummyHead;
while (cur->next != NULL) {
cur = cur->next;
}
cur->next = newNode;
size++;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
ListNode* newNode = new ListNode(val);
ListNode* cur = dummyHead;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
size++;
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
ListNode* cur = dummyHead;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
ListNode* tmp = cur->next;
cur->next = tmp->next;
delete tmp;
size--;
}
/** Swap the odd and even nodes of the linked list. */
void swapNodes() {
if (size < 2) {
return;
}
ListNode* odd = dummyHead->next;
ListNode* even = dummyHead->next->next;
while (even != NULL && even->next != NULL) {
ListNode* tmp = odd->next;
odd->next = even->next;
even->next = even->next->next;
odd->next->next = tmp;
odd = odd->next;
even = even->next;
}
}
/** Move the first i nodes of the linked list to the end of the linked list. */
void move(int i) {
if (i >= size) {
return;
}
ListNode* cur = dummyHead;
for (int j = 0; j < i; j++) {
cur = cur->next;
}
ListNode* tail = cur;
while (tail->next != NULL) {
tail = tail->next;
}
tail->next = dummyHead->next;
dummyHead->next = cur->next;
cur->next = NULL;
}
/** Print the value of the index-th node in the linked list. If the index is invalid, do nothing. */
void print(int index) {
if (index >= 0 && index < size) {
ListNode* cur = dummyHead->next;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
cout << cur->val << endl;
}
}
/** Print the entire linked list. */
void printList() {
ListNode* cur = dummyHead->next;
while (cur != NULL) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
ListNode* dummyHead;
int size;
};
int main() {
int n, m;
cin >> n;
MyLinkedList linkedList;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
linkedList.addAtTail(x);
}
cin >> m;
while (m--) {
int op;
cin >> op;
if (op == 1) {
int index, val;
cin >> index >> val;
linkedList.addAtIndex(index, val);
} else if (op == 2) {
int index;
cin >> index;
linkedList.deleteAtIndex(index);
} else if (op == 3) {
linkedList.swapNodes();
} else if (op == 4) {
int i, x;
cin >> i >> x;
linkedList.move(i);
} else if (op == 5) {
int index;
cin >> index;
linkedList.print(index);
} else if (op == 6) {
linkedList.printList();
}
}
return 0;
}
```
这段代码实现了一个单链表,支持题目中所要求的六个操作。其中,get、addAtHead、addAtTail、addAtIndex、deleteAtIndex、print、printList 函数分别对应题目中的操作。swapNodes 函数为交换奇偶位的操作函数,move 函数为整体移动操作函数。
阅读全文