创建一个由6个结点的单向链表,实现结点的增加、删除、查找、移动、遍历显示等功能。
时间: 2023-12-21 20:06:23 浏览: 48
好的,我可以为您解答这个问题。
首先,我们需要定义一个链表结构体,包含一个头指针和一个大小成员变量。
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class MyLinkedList {
public:
/** Initialize your data structure here. */
MyLinkedList() {
head = NULL;
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 *curr = head;
for (int i = 0; i < index; ++i)
curr = curr->next;
return curr->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 *node = new ListNode(val);
node->next = head;
head = node;
++size;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
if (head == NULL)
return addAtHead(val);
ListNode *node = new ListNode(val);
ListNode *curr = head;
while (curr->next != NULL)
curr = curr->next;
curr->next = node;
++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 <= 0)
return addAtHead(val);
if (index == size)
return addAtTail(val);
if (index > size)
return;
ListNode *node = new ListNode(val);
ListNode *curr = head;
for (int i = 0; i < index-1; ++i)
curr = curr->next;
node->next = curr->next;
curr->next = node;
++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;
if (index == 0)
head = head->next;
else {
ListNode *curr = head;
for (int i = 0; i < index-1; ++i)
curr = curr->next;
curr->next = curr->next->next;
}
--size;
}
/** Print all elements in the linked list. */
void print() {
ListNode *curr = head;
while (curr != NULL) {
cout << curr->val << " ";
curr = curr->next;
}
cout << endl;
}
/** Move the index-th node to the beginning of the linked list. */
void moveToHead(int index) {
if (index <= 0 || index >= size)
return;
ListNode *prev = NULL, *curr = head;
for (int i = 0; i < index; ++i) {
prev = curr;
curr = curr->next;
}
prev->next = curr->next;
curr->next = head;
head = curr;
}
private:
ListNode *head;
int size;
};
可以按照上述代码实现链表中的各种操作。注意在实现移动操作时,需要借助前驱节点指针,将要移动的节点插入到链表头部即可。
阅读全文