设计单链表
要求
题目要我们实现有关单链表的基本操作，即以下几个函数：
MyLinkedList* myLinkedListCreate() //创建单链表 int myLinkedListGet(MyLinkedList* obj, int index) //得到下标为index的节点的值，如果index无效则返回-1 void myLinkedListAddAtHead(MyLinkedList* obj, int val) //链表头插 void myLinkedListAddAtTail(MyLinkedList* obj, int val) //链表尾插 void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) //在下标index处插入值为val的节点，如果index等于链表长度，则相当于尾插 void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) //删除下标为index的节点，如果index无效，则不操作 void myLinkedListFree(MyLinkedList* obj) //删除链表
解析函数形参
- 我们知道，单链表有带哨兵位（头一个节点为无效节点）和不带哨兵位（第一个节点就存储有效数据）两种形式，而二者在用法上的主要区别，就是在对头结点的处理上
- 例如，如果我们要删除链表第一个有效节点，若我们的链表有哨兵位，那就好办，直接让哨兵位链接到第二个节点即可，但如果我们的链表没有哨兵位呢？那操作就不是删除第一个节点然后返回第二个节点这么简单了，因为我们知道，函数的形参只是实参的一份临时拷贝，对形参的修改不会影响实参，也就是说，在函数中删除我们的第一个节点，实际上实参的头节点仍然存在，因此如果想要对无哨兵位的链表进行头删操作，就要传入头节点的二级指针，这样才能达到要求。
- 我们看到题目所给的函数形参传入的是一级指针，因此显然，我们要使用带哨兵位的链表。
实现代码
typedef struct List { int val; struct List *next; } MyLinkedList; //初始化单链表 MyLinkedList* myLinkedListCreate() { MyLinkedList *head = (MyLinkedList *)malloc(sizeof(MyLinkedList)); head->next = NULL; return head; } //得到下标为index的节点的值，如果index无效则返回-1 int myLinkedListGet(MyLinkedList* obj, int index) { MyLinkedList *cur = obj->next; //第一个节点不存储有效数据，因此从后一个节点开始计数 int count = 0; while(cur) { if(count == index) return cur->val; cur = cur->next; count++; } return -1; } //头插 void myLinkedListAddAtHead(MyLinkedList* obj, int val) { //创建新节点 MyLinkedList *newHead = (MyLinkedList*)malloc(sizeof(MyLinkedList)); newHead->val = val; newHead->next = NULL; //如果链表为空 if(obj->next == NULL) obj->next = newHead; //如果链表不为空 else { newHead->next = obj->next; obj->next = newHead; } } //尾插 void myLinkedListAddAtTail(MyLinkedList* obj, int val) { //创建尾节点 MyLinkedList *newHead = (MyLinkedList*)malloc(sizeof(MyLinkedList)); newHead->val = val; newHead->next = NULL; //找到链表的尾 MyLinkedList *cur = obj; while(cur->next) cur = cur->next; //实现插入 cur->next = newHead; } //在下标index处插入值为val的节点，如果index等于链表长度，则相当于尾插 void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) { //如果index为0，相当于头插 if(index == 0) { myLinkedListAddAtHead(obj,val); return; } MyLinkedList *newHead = (MyLinkedList*)malloc(sizeof(MyLinkedList)); //新建节点 //第一个节点不存储有效数据，因此从后一个节点开始计数，同时定义一个指针记录cur的前一个节点便于插入 MyLinkedList *cur = obj->next, *pre = obj; newHead->val = val; int count = 0; while(cur) { //如果index大于0小于链表长度 if(count == index && cur != NULL) { pre->next = newHead; newHead->next = cur; return; } pre = cur; cur = cur->next; count++; } //如果index等于链表长度，直接尾插 if(count == index && cur == NULL) { myLinkedListAddAtTail(obj,val); return; } //index不合法，直接return return; } //删除下标为index的节点，如果index无效，则不操作 void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) { //第一个节点不存储有效数据，因此从后一个节点开始计数，同时定义一个指针记录cur的前一个节点便于删除 MyLinkedList *cur = obj->next, *pre = obj; int count = 0; while(cur) { if(count == index) { pre->next = cur->next; free(cur); return; } pre = cur; cur = cur->next; count++; } return; } //销毁链表 void myLinkedListFree(MyLinkedList* obj) { MyLinkedList *cur = obj->next; while(cur) { MyLinkedList *temp = cur->next; //定义temp记录cur的下一个位置 free(cur); cur = temp; } }
