leetcode 707. 设计链表
一.题目描述
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
示例：
输入 ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] 输出 [null, null, null, null, 2, null, 3] 解释 MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3 myLinkedList.get(1); // 返回 3
二.思路分析
1.大体思路
先在类里面创建结构体，制造链表所包含的要求，再分析每一个函数所要求的，最后析构即可。
2.细节
（1）结构体的设置
设置结构体的时候，要设置一个有参构造，以应对新的ListNode的插入，同时要在结构体外部设置一个头指针head和用来表示链表大小的size。
（2）int get部分
首先要注意的是，判断index是否合法的条件是<0和>=size，这里的>=size是因为我们的链表是从0开始末尾的那个链表部分的序号是size-1，接下来就是用cur指针便利了.
（3）void addAtHead部分
这里要注意的是这两行代码不能颠倒顺序，应为颠倒后newNode->next指向不了你所需的先前的head.
newNode->next=head; head=newNode;（4）void addAtTail部分
首先要判断是否为空链表，若为空则，直接使head指向newhead即可
若不为空，则让cur遍历到链表最后端即可。
（5）void addAtIndex部分
首先要判断是否合法，同（2）部分，然后就是单独把头部插入和尾部插入分别单列出来，调用以上所写的函数即可，没必要再写一遍,中间部分正常便利即可
或者整个函数用dummyhead实现也可以:
void addAtIndex(int index, int val) { if (index < 0 || index > size) { return; } ListNode dummy(0); dummy.next=head; ListNode* newNode=new ListNode(val); ListNode* cur=&dummy; while(index--) { cur=cur->next; } newNode->next=cur->next; cur->next=newNode; head=dummy.next; size++; }这里要注意的是，用dummy时，可能用例子把head所指的链表更新了，所以在倒数第二行有一句head=dummy.next，更新表头，这部分可以完美替换“三”中的相应部分。
（6）void deleteAtIndex部分
可以把头部的情况单独写一下，再用以上相同的方法遍历即可
后者用dummy也可以：
void deleteAtIndex(int index) { if(index<0||index>=size) return; ListNode dummy(0); dummy.next=head; ListNode* cur=&dummy; while(index--) { cur=cur->next; } ListNode* temp = cur->next; cur->next=cur->next->next; delete temp; head=dummy.next; size--; }这里delete是防止内存泄漏，为了通过的话，也可以不用
（7）~MyLinkedList部分
从head开始遍历，释放链表，因为这里cur是用来遍历的，所以，要用temp来过度一下，可写可不写，随意，严谨就写，不写也能通过
三.代码实现
class MyLinkedList { private: struct ListNode { int val; ListNode* next; ListNode(int x):val(x),next(nullptr){} }; ListNode* head; int size; public: MyLinkedList() { head=nullptr; size=0; } int get(int index) { if(index<0||index>=size) return -1; ListNode* cur=head; for(int i=0;i<index;i++) { cur=cur->next; } return cur->val; } void addAtHead(int val) { ListNode* newNode= new ListNode(val); newNode->next=head; head=newNode; size++; } void addAtTail(int val) { ListNode* newNode=new ListNode(val); if(head==nullptr) { head=newNode; } else { ListNode* cur=head; while(cur->next!=nullptr) { cur=cur->next; } cur->next=newNode; } size++; } void addAtIndex(int index, int val) { if(index<0||index>size) return; if(index==0) { addAtHead(val); return; } if(index==size) { addAtTail(val); return; } ListNode* cur=head; for(int i=0;i<index-1;i++) { cur=cur->next; } ListNode* newNode=new ListNode(val); newNode->next=cur->next; cur->next=newNode; size++; } void deleteAtIndex(int index) { if(index<0||index>=size) return; if(index==0) { ListNode* temp=head; head=head->next; delete temp; } else { ListNode* cur=head; for(int i=0;i<index-1;i++) { cur=cur->next; } ListNode* temp=cur->next; cur->next=cur->next->next; delete temp; } size--; } ~MyLinkedList() { ListNode* cur=head; while(cur!=nullptr) { ListNode* temp=cur; cur=cur->next; delete temp; } } };
