【LeetCode 07】707. 设计链表
文章目录
一、题意
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
题目中给出了结点定义：
typedef struct {//定义节点
} MyLinkedList;
//初始化链表
MyLinkedList* myLinkedListCreate() {
}
//获取第index个节点的数值,如果index是非法值返回-1
int myLinkedListGet(MyLinkedList* obj, int index) {
}
//在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
}
//将值为 val 的节点追加到链表的最后一个元素。
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
}
//在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
}
//删除第index个节点，如果index大于或等于链表的长度，则直接返回
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
}
void myLinkedListFree(MyLinkedList* obj) {
}
/**
* Your MyLinkedList struct will be instantiated and called as such:
* MyLinkedList* obj = myLinkedListCreate();
* int param_1 = myLinkedListGet(obj, index);
* myLinkedListAddAtHead(obj, val);
* myLinkedListAddAtTail(obj, val);
* myLinkedListAddAtIndex(obj, index, val);
* myLinkedListDeleteAtIndex(obj, index);
* myLinkedListFree(obj);
*/
二、思考过程
2.1定义节点及其信息
定义指针域，数据域：
typedef struct {//定义节点
int val;//数据域
struct MyLinkedList *next;//指针域
} MyLinkedList;
2.2初始化链表
//初始化链表
MyLinkedList* myLinkedListCreate() {
MyLinkedList *head=(MyLinkedList *)malloc(sizeof(MyLinkedList));//虚拟头指针，开辟内存空间
head->next=NULL;
return head;
}
2.3获取第index个节点的数值
//获取第index个节点的数值,如果index是非法值返回-1
int myLinkedListGet(MyLinkedList* obj, int index) {
MyLinkedList *cur=obj->next;
for(int i=0;cur!=NULL;i++){
if(i==index){
return cur->val;
}else{
cur=cur->next;
}
}
return -1;
}
2.4插入后，新节点将成为链表的第一个节点。
//在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
MyLinkedList *nhead=(MyLinkedList *)malloc(sizeof(MyLinkedList));
nhead->val=val;
nhead->next=obj->next;
obj->next=nhead;
}
2.5将值为 val 的节点追加到链表的最后一个元素。
//将值为 val 的节点追加到链表的最后一个元素。
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
MyLinkedList *cur=obj;
while(cur->next!=NULL){
cur=cur->next;
}
MyLinkedList *ntail=(MyLinkedList *)malloc(sizeof(MyLinkedList));
ntail->val=val;
ntail->next=NULL;
cur->next=ntail;
}
2.6在链表中的第 index 个节点之前添加值为 val 的节点
//在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
if(index==0){
myLinkedListAddAtHead(obj,val);
return;
}
MyLinkedList *cur=obj->next;
for(int i=1;cur!=NULL;i++){
if(i==index){
MyLinkedList *newnode=(MyLinkedList *)malloc(sizeof(MyLinkedList));
newnode->val=val;
newnode->next=cur->next;
cur->next=newnode;
return;
}else{
cur=cur->next;
}
}
}
2.6删除第index个节点
//删除第index个节点，如果index大于或等于链表的长度，则直接返回
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
if(index==0){
MyLinkedList *tmp=obj->next;
if(tmp!=NULL){
obj->next=tmp->next;
free(tmp);
}
return;
}
MyLinkedList *cur=obj->next;
for(int i=1;cur!=NULL&&cur->next!=NULL;i++){
if(i==index){
MyLinkedList *tmp=cur->next;
if(tmp!=NULL){
cur->next=tmp->next;
free(tmp);
}
return;
}else{
cur=cur->next;
}
}
}
2.7释放链表
//释放链表
void myLinkedListFree(MyLinkedList* obj) {
while(obj!=NULL){
MyLinkedList *tmp=obj;
obj=obj->next;
free(tmp);
}
}
三、完整代码
typedef struct {//定义节点
int val;
struct MyLinkedList* 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;
for(int i=0;cur!=NULL;i++){
if(i==index){
return cur->val;
}else{
cur=cur->next;
}
}
return -1;
}
//在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
MyLinkedList *nhead=(MyLinkedList *)malloc(sizeof(MyLinkedList));
nhead->val=val;
nhead->next=obj->next;
obj->next=nhead;
}
//将值为 val 的节点追加到链表的最后一个元素。
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
MyLinkedList *cur=obj;
while(cur->next!=NULL){
cur=cur->next;
}
MyLinkedList *ntail=(MyLinkedList *)malloc(sizeof(MyLinkedList));
ntail->val=val;
ntail->next=NULL;
cur->next=ntail;
}
//在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
if(index==0){
myLinkedListAddAtHead(obj,val);
return;
}
MyLinkedList *cur=obj->next;
for(int i=1;cur!=NULL;i++){
if(i==index){
MyLinkedList *newnode=(MyLinkedList *)malloc(sizeof(MyLinkedList));
newnode->val=val;
newnode->next=cur->next;
cur->next=newnode;
return;
}else{
cur=cur->next;
}
}
}
//删除第index个节点，如果index大于或等于链表的长度，则直接返回
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
if(index==0){
MyLinkedList *tmp=obj->next;
if(tmp!=NULL){
obj->next=tmp->next;
free(tmp);
}
return;
}
MyLinkedList *cur=obj->next;
for(int i=1;cur!=NULL&&cur->next!=NULL;i++){
if(i==index){
MyLinkedList *tmp=cur->next;
if(tmp!=NULL){
cur->next=tmp->next;
free(tmp);
}
return;
}else{
cur=cur->next;
}
}
}
//释放链表
void myLinkedListFree(MyLinkedList* obj) {
while(obj!=NULL){
MyLinkedList *tmp=obj;
obj=obj->next;
free(tmp);
}
}
/**
* Your MyLinkedList struct will be instantiated and called as such:
* MyLinkedList* obj = myLinkedListCreate();
* int param_1 = myLinkedListGet(obj, index);
* myLinkedListAddAtHead(obj, val);
* myLinkedListAddAtTail(obj, val);
* myLinkedListAddAtIndex(obj, index, val);
* myLinkedListDeleteAtIndex(obj, index);
* myLinkedListFree(obj);
*/