LeetCode 707 题：设计链表
LeetCode 707 题：设计链表（Design Linked List）
题目描述
设计一个支持以下操作的链表实现：
MyLinkedList(): 设计并初始化一个空链表。get(index): 获取链表中第index个节点的值。如果索引无效，则返回 -1。addAtHead(val): 在链表的第一个元素前添加一个值为val的节点。addAtTail(val): 在链表的最后一个元素后添加一个值为val的节点。addAtIndex(index, val): 在链表的第index个节点之前添加值为val的节点。如果index大于链表的长度，则不会插入节点。deleteAtIndex(index): 删除链表中第index个节点，如果索引无效，则不删除节点。
解题思路
我们可以使用链表来实现这些功能，链表的基本操作包括：在头部插入、尾部插入、按索引插入、删除元素。为了高效实现这些操作，我们需要：
addAtHead()和addAtTail()都是常数时间操作。addAtIndex()和deleteAtIndex()需要通过遍历链表找到指定的位置，因此它们的时间复杂度为 O ( n ) O(n) O(n)，其中 n n n 是链表的长度。
我们使用虚拟头节点来简化边界条件的处理。
代码实现与逐行详解
#include <stdio.h>
#include <stdlib.h>
// 链表节点结构
struct ListNode {
int val;
struct ListNode *next;
};
// 链表类
struct MyLinkedList {
struct ListNode *head;
};
// 创建一个新节点
struct ListNode* createNode(int val) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 初始化链表
struct MyLinkedList* myLinkedListCreate() {
struct MyLinkedList* obj = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
obj->head = createNode(0); // 创建一个虚拟头节点，简化操作
return obj;
}
// 获取链表第 index 个节点的值
int myLinkedListGet(struct MyLinkedList* obj, int index) {
struct ListNode* current = obj->head->next; // 从虚拟头节点的下一个开始
for (int i = 0; i < index && current != NULL; i++) {
current = current->next;
}
return (current == NULL) ? -1 : current->val;
}
// 在链表头部添加一个值为 val 的节点
void myLinkedListAddAtHead(struct MyLinkedList* obj, int val) {
struct ListNode* newNode = createNode(val);
newNode->next = obj->head->next;
obj->head->next = newNode;
}
// 在链表尾部添加一个值为 val 的节点
void myLinkedListAddAtTail(struct MyLinkedList* obj, int val) {
struct ListNode* newNode = createNode(val);
struct ListNode* current = obj->head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
// 在链表第 index 个位置之前添加一个值为 val 的节点
void myLinkedListAddAtIndex(struct MyLinkedList* obj, int index, int val) {
if (index < 0) return;
struct ListNode* current = obj->head;
for (int i = 0; i < index && current != NULL; i++) {
current = current->next;
}
if (current == NULL) return; // 如果当前节点为空，说明索引超出链表长度
struct ListNode* newNode = createNode(val);
newNode->next = current->next;
current->next = newNode;
}
// 删除链表第 index 个位置的节点
void myLinkedListDeleteAtIndex(struct MyLinkedList* obj, int index) {
struct ListNode* current = obj->head;
for (int i = 0; i < index && current != NULL; i++) {
current = current->next;
}
if (current == NULL || current->next == NULL) return; // 索引无效，或者没有需要删除的节点
struct ListNode* toDelete = current->next;
current->next = current->next->next;
free(toDelete);
}
// 释放链表
void myLinkedListFree(struct MyLinkedList* obj) {
struct ListNode* current = obj->head;
while (current != NULL) {
struct ListNode* toDelete = current;
current = current->next;
free(toDelete);
}
free(obj);
}
// 打印链表
void printList(struct MyLinkedList* obj) {
struct ListNode* current = obj->head->next;
while (current != NULL) {
printf("%d -> ", current->val);
current = current->next;
}
printf("NULL\n");
}
代码逐行详解
1. 链表节点结构体定义
struct ListNode {
int val;
struct ListNode *next;
};
- 链表节点定义：定义了一个链表节点
ListNode，包含两个成员：val：节点的值。next：指向下一个节点的指针。
2. 创建新节点函数
struct ListNode* createNode(int val) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
- 创建节点：通过
malloc动态分配内存，创建一个新的节点，并初始化节点的值和next指针。
3. MyLinkedList 结构体与初始化
struct MyLinkedList* myLinkedListCreate() {
struct MyLinkedList* obj = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
obj->head = createNode(0); // 创建一个虚拟头节点，简化操作
return obj;
}
- 初始化链表：创建一个
MyLinkedList对象，并为其分配内存。为了简化链表操作，创建了一个虚拟头节点head，初始值为 0。
4. 获取链表第 index 个节点的值
int myLinkedListGet(struct MyLinkedList* obj, int index) {
struct ListNode* current = obj->head->next;
for (int i = 0; i < index && current != NULL; i++) {
current = current->next;
}
return (current == NULL) ? -1 : current->val;
}
- 获取节点值：从链表头节点开始，遍历到第
index个节点。如果找到了该节点，则返回其值；否则返回-1。
5. 在链表头部添加节点
void myLinkedListAddAtHead(struct MyLinkedList* obj, int val) {
struct ListNode* newNode = createNode(val);
newNode->next = obj->head->next;
obj->head->next = newNode;
}
- 在头部插入节点：创建一个新节点并将其插入到链表的头部。更新虚拟头节点
head的next指针指向新节点。
6. 在链表尾部添加节点
void myLinkedListAddAtTail(struct MyLinkedList* obj, int val) {
struct ListNode* newNode = createNode(val);
struct ListNode* current = obj->head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
- 在尾部插入节点：遍历链表直到找到最后一个节点，将新节点插入到该节点的
next指针位置。
7. 在指定索引处添加节点
void myLinkedListAddAtIndex(struct MyLinkedList* obj, int index, int val) {
if (index < 0) return;
struct ListNode* current = obj->head;
for (int i = 0; i < index && current != NULL; i++) {
current = current->next;
}
if (current == NULL) return;
struct ListNode* newNode = createNode(val);
newNode->next = current->next;
current->next = newNode;
}
原文地址：https://blog.csdn.net/weixin_48941116/article/details/145235077
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！