1.虚拟头结点
203. 移除链表元素 - 力扣（LeetCode）
class Solution { public: ListNode* removeElements(ListNode* head, int val) { int v=val; ListNode*dummyhead=new ListNode(0); dummyhead->next=head; head=dummyhead; ListNode*cur=head; while(cur->next!=nullptr) { if(cur->next->val==v) { ListNode*tmp=cur->next; cur->next=cur->next->next; delete tmp; }else{ cur=cur->next; } } head=dummyhead->next; delete dummyhead; return head; } };写的时候总是超时，最后才发现是忘记写cur=cur->next了....
这里要注意是否删除对应的cur结点位置变化
707. 设计链表 - 力扣（LeetCode）
class MyLinkedList { private: struct ListNode{ int val; ListNode*next; ListNode(int x=0):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*dummyhead=new ListNode(0); dummyhead->next=head; head=dummyhead; ListNode*newNode=new ListNode(val); ListNode*cur=head; for(int i=0;i<size;++i) { cur=cur->next; } newNode->next=cur->next; cur->next=newNode; head=head->next; delete dummyhead; ++size; } void addAtIndex(int index, int val) { if(index>size||index<0){ return; } ListNode*dummyhead=new ListNode(0); dummyhead->next=head; head=dummyhead; ListNode*newNode=new ListNode(val); ListNode*cur=head; for(int i=0;i<index;++i) { cur=cur->next; } newNode->next=cur->next; cur->next=newNode; head=head->next; delete dummyhead; ++size; } void deleteAtIndex(int index) { if(index<0||index>=size) { return; } ListNode*dummyhead=new ListNode(0); dummyhead->next=head; head=dummyhead; ListNode*cur=head; for(int i=0;i<index;++i) { cur=cur->next; } ListNode*tmp=cur->next; cur->next=tmp->next; delete tmp; head=head->next; delete dummyhead; size--; } };206. 反转链表 - 力扣（LeetCode）
class Solution { public: ListNode* reverseList(ListNode* head) { if(head==nullptr){ return nullptr; } ListNode*dummyhead=new ListNode(0); dummyhead->next=head; head=dummyhead; ListNode*cur=head->next; stack<ListNode*>Nodestack; while(cur!=NULL){ Nodestack.push(cur); cur=cur->next; } ListNode*cu=head; while(!Nodestack.empty()) { ListNode*tm=Nodestack.top(); Nodestack.pop(); cu->next=tm; cu=cu->next; } cu->next=nullptr; return head->next; } };19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode*dummyhead=new ListNode(0); dummyhead->next=head; head=dummyhead; ListNode*fast=head; ListNode*slow=head; fast=fast->next; while(n--&&fast!=NULL) { fast=fast->next; } while(fast!=NULL) { fast=fast->next; slow=slow->next; } ListNode*tmp=slow->next; slow->next=slow->next->next; delete tmp; return head->next; } };这里用虚拟头结点主要是因为想要避免为了得到删除节点的前一个节点，而对删除节点为头结点时的单独讨论
2.双指针
206. 反转链表 - 力扣（LeetCode）
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode*temp; ListNode*pre=nullptr; ListNode*cur=head; while(cur) { temp=cur->next; cur->next=pre; pre=cur; cur=temp; } return pre; } };
