给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
虚拟头结点法：
1 ListNode* removeElements(ListNode* head, int val) {
2 //创建虚拟头结点
3 ListNode* _dummyHead = new ListNode(0);
4 //使虚拟头结点指向原来的头结点
5 _dummyHead->next = head;
6 //创建索引要用的结点
7 ListNode* cur = _dummyHead;
8 //当cur->next != nullptr 持续向后查找
9 while (cur->next != nullptr){
10 if (cur->next->val == val){
11 //锁定值为val的结点
12 ListNode* tmp = cur->next;
13 //将cur指向下下个结点
14 cur->next = cur->next->next;
15 //删除值为val的结点
16 delete tmp;
17 } else {
18 cur = cur->next;
19 }
20 }
21 head = _dummyHead->next;
22 //删除虚拟头结点
23 delete _dummyHead;
24 return head;
25 }
直接删除法：
1 ListNode* removeElements(ListNode* head, int val) {
2 //删除头节点
3 //新的头结点的值仍有可能为0
4 while (head != nullptr && head->val == val){
5 ListNode* tmp = head;
6 head = head->next;
7 delete tmp;
8 }
9
10 //删除非头节点
11 ListNode* cur = head;
12 while (cur != nullptr && cur->next != nullptr){
13 if (cur->next->val == val){
14 ListNode* tmp = cur->next;
15 cur->next = cur->next->next;
16 delete tmp;
17 } else {
18 cur = cur->next;
19 }
20 }
21 return head;
22 }
707.设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
定义链表结构体：
1 // 定义链表节点结构体
2 struct LinkedNode {
3 int val;
4 LinkedNode* next;
5 LinkedNode(int val):val(val), next(nullptr){}
6 };
初始化链表：
1 // 初始化链表
2 MyLinkedList() {
3 _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
4 _size = 0;
5 }
获取第index个结点的值：
1 // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
2 int get(int index) {
3 if (index > (_size - 1) || index < 0) {
4 return -1;
5 }
6 LinkedNode* cur = _dummyHead->next;
7 while(index--){ // 如果--index 就会陷入死循环
8 cur = cur->next;
9 }
10 return cur->val;
11 }
在链表头部插入一个结点：
1 // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
2 void addAtHead(int val) {
3 LinkedNode* newNode = new LinkedNode(val);
4 newNode->next = _dummyHead->next;
5 _dummyHead->next = newNode;
6 _size++;
7 }
在链表尾部插入一个结点：
1 // 在链表最后面添加一个节点
2 void addAtTail(int val) {
3 LinkedNode* newNode = new LinkedNode(val);
4 LinkedNode* cur = _dummyHead;
5 while(cur->next != nullptr){
6 cur = cur->next;
7 }
8 cur->next = newNode;
9 _size++;
10 }
在第index个结点前插入一个值为val的结点
1 // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
2 // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
3 // 如果index大于链表的长度，则返回空
4 // 如果index小于0，则置为0，作为链表的新头节点。
5 void addAtIndex(int index, int val) {
6 if (index > _size || index < 0) {
7 return;
8 }
9 LinkedNode* newNode = new LinkedNode(val);
10 LinkedNode* cur = _dummyHead;
11 while(index--) {
12 cur = cur->next;
13 }
14 newNode->next = cur->next;
15 cur->next = newNode;
16 _size++;
17 }
删除第index个结点
1 // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
2 void deleteAtIndex(int index) {
3 if (index >= _size || index < 0) {
4 return;
5 }
6 LinkedNode* cur = _dummyHead;
7 while(index--) {
8 cur = cur ->next;
9 }
10 LinkedNode* tmp = cur->next;
11 cur->next = cur->next->next;
12 delete tmp;
13 _size--;
14 }
打印链表：
1 // 打印链表
2 void printLinkedList() {
3 LinkedNode* cur = _dummyHead;
4 while (cur->next != nullptr) {
5 cout << cur->next->val << " ";
6 cur = cur->next;
7 }
8 cout << endl;
9 }
206. 反转链表
双指针法：
双指针初始化：
//使得尾结点指向pulltr
ListNode* pre = nullptr;
//cur为头结点
ListNode* cur = head;
//创建临时节点用于记录cur->next
ListNode* tmp;
当cur != nullptr 时，持续反转：
1 while (cur != nullptr){
2 //记录cur->next
3 tmp = cur->next;
4 //关键反转操作
5 cur->next = pre;
6 //cur,pre向后移动
7 pre = cur;
8 cur = tmp;
9 }
递归法：
1 class Solution {
2 public:
3 ListNode* reverse(ListNode* pre,ListNode* cur){
4 if (cur == nullptr) return pre;
5 ListNode* tmp = cur->next;
6 cur->next = pre;
7 return reverse(cur, tmp);
8 }
9 ListNode* reverseList(ListNode* head) {
10 return reverse(nullptr, head);
11 }
12 };
标签：index,cur,val,随想录,next,链表,移除,节点 From： https://www.cnblogs.com/zsqy/p/16731127.html