[数据结构与算法]leetcode 707 设计链表

该题目覆盖了链表的常见操作，非常适合初学者巩固链表相关知识。
leetocde原题链接

//单链表方法
//这个题必须用虚拟头指针（即设头节点）
//首元节点是第0个节点
typedef struct {
    int val;
    struct MyLinkedList *next;
} MyLinkedList;

/** Initialize your data structure here. 初始化数据结构。*/

MyLinkedList* myLinkedListCreate() 
{
    MyLinkedList* head = (MyLinkedList *)malloc(sizeof (MyLinkedList));
    head->next = NULL;
    return head;
}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int myLinkedListGet(MyLinkedList* obj, int index) 
{
    int i = 0;
    if(obj->next == NULL)//考虑链表为空情况
        return -1;
    MyLinkedList *p = obj->next; 
    while(true)
    {
    	if (i == index)
        	return p->val;
    	p = p->next;
    	i++;
    	if (p == NULL)
        	return -1;
    }
    return 0;  //没什么用,但由于返回值在函数中间,这样可以防止报错
}

/** 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 myLinkedListAddAtHead(MyLinkedList* obj, int val)
{
    MyLinkedList *p = (MyLinkedList *)malloc(sizeof(MyLinkedList));   
    p->val = val;
    p->next = obj->next; //头插法
    obj->next = p; //改变头节点
}
 
/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(MyLinkedList* obj, int val)
{
    MyLinkedList *t = obj;
    MyLinkedList *p = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    while(t->next)
    {
        t = t->next;
    }
    p->val = val;
    t->next = p;
    p->next = NULL;
}

    
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val)
{
    MyLinkedList *t = obj;
    MyLinkedList *p = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    p->val = val;
    int i = 0;
    if(index <= 0)
    {
    	p->next = obj->next;
        obj->next = p;
    }
    else if(index > 0)
    {
        for(i = 1; t!= NULL; i++)
        {
        	t = t->next;
            if(index == i && t->next != NULL)
            {
                p->next = t->next;
                t->next = p;
            }
            if(index == i && t->next == NULL)//考虑index等于链表长度情况
            {
                p->next = NULL;
                t->next = p;
            }
        }
    }
}


void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index)
{
    MyLinkedList *t = obj->next, *c = obj;
    int i = 0;
    while(t->next != NULL)
    {
        if(index == i)
        {
            c->next = t->next;
            free(t);
            return;
        }
        t = t->next;
        c = c->next;
        i++;
    }
    if(index == i)
    {
        c->next = NULL;
        free(t);
    }
}



void myLinkedListFree(MyLinkedList* obj)
{
        while(obj != NULL)
        {
        MyLinkedList *t = obj;
        obj = obj->next;
        free(t);
        }
}

/**
 * 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);
*/