LeetCode 707 题：设计链表（Design Linked List）

题目描述

设计一个支持以下操作的链表实现：

1. MyLinkedList(): 设计并初始化一个空链表。
2. get(index): 获取链表中第 index 个节点的值。如果索引无效，则返回 -1。
3. addAtHead(val): 在链表的第一个元素前添加一个值为 val 的节点。
4. addAtTail(val): 在链表的最后一个元素后添加一个值为 val 的节点。
5. addAtIndex(index, val): 在链表的第 index 个节点之前添加值为 val 的节点。如果 index 大于链表的长度，则不会插入节点。
6. deleteAtIndex(index): 删除链表中第 index 个节点，如果索引无效，则不删除节点。

解题思路

我们可以使用链表来实现这些功能，链表的基本操作包括：在头部插入、尾部插入、按索引插入、删除元素。为了高效实现这些操作，我们需要：

1. addAtHead() 和 addAtTail() 都是常数时间操作。
2. addAtIndex() 和 deleteAtIndex() 需要通过遍历链表找到指定的位置，因此它们的时间复杂度为 $O(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;
}