1.T203：移除链表元素

T：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

S：因为单链表的特殊性，只能指向下一个节点，如果删除的是头结点该怎么办呢？

这里就涉及如下链表操作的两种方式：

直接使用原来的链表来进行删除操作。
设置一个虚拟头结点在进行删除操作。

因为自己最开始也是学C++出身的，再加上链表部分的代码不像前面的数组，C++和Java的代码相似度相当高，而是在C++中大量用到了指针，因此，为了更好地感受链表数据结构，决定用两种语言都写一遍（如下所见，就我个人而言，主要有3个注意点）~

1.1.法一：直接使用原来的链表操作（比较好理解）

C++：

    ListNode* removeElements(ListNode* head, int val) {//删除头节点while (head != NULL && head->val == val) {//不能写成ifListNode* temp = head;//1、不设置临时指针的话，下两行不论先后都无法全部成功head = head -> next;delete temp;}//删除非头节点ListNode* cur = head;//要理解为什么不是head->nextwhile (cur != NULL && cur->next != NULL) {if (cur->next->val == val) {ListNode* temp = cur->next;//1、设置临时指针的原因同上cur->next = cur->next->next;//cur->next->next可以为NULLdelete temp;} else {cur = cur->next;}}return head;}

Java：

    public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}//删除头节点while (head != null && head.val == val) {head = head.next;}//删除非头结点ListNode cur = head;while (cur != null && cur.next != null) {if (cur.next.val == val) {cur.next = cur.next.next;} else {cur = cur.next;}}return head;}

1.2.法二：设置一个虚拟头节点再操作（更通用的更优解）

C++：

    //自己复现的ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(-1, head);ListNode* cur = dummyHead;while (cur != NULL && cur->next != NULL) {if (cur->next->val == val) {ListNode* temp = cur->next;cur->next = cur->next->next;//3、等同于改变了dummyHead->nextdelete temp;//2、等于delete原来的cur->next} else {cur = cur->next;}}// return dummyHead->next;//也可以等效于下面三行，只是没释放dummyHead指向的内存空间head = dummyHead->next;delete dummyHead;//等于delete curreturn head;}

Java：

    public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}ListNode dummyHead = new ListNode(-1, head);ListNode cur = dummyHead;while (cur != null && cur.next != null) {if (cur.next.val == val) {cur.next = cur.next.next;//3、写法不同于C++，但遇到头节点时的作用是一样的} else {cur = cur.next;}}head = dummyHead.next;//  head = cur.next;//错误return head;}

2.T707：设计链表

T：设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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 个节点

S：起初，如下写法，结果：

java.lang.NullPointerException: Cannot read field "val" because "<local2>" is null

at line 33, MyLinkedList.get

at line 63, __Driver__.__helperSelectMethod__

at line 99, __Driver__.__helper__

at line 120, __Driver__.main

虽然显示33行报错，但实际上问题并不在此，而是出在链表头节点定义相关的逻辑上

class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}class MyLinkedList {int size;ListNode head;//🚩这里在思想上犯了一个根本性的错误，那就是以为是初始化了一个真的头节点！public MyLinkedList() {size = 0;//初始化的时候size为0，可见下一行的head也就相当于是一个dummyHeadhead = new ListNode(0);}//获取第index个节点的数值（从0开始）public 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;return cur.val;//虽然此行报错，但实际上错不在此，而是插入的时候就已经失败了}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}public void addAtIndex(int index, int val) {if(index < 0 || index > size)return;// ListNode dummyHead = new ListNode(-1, head);ListNode addNode = new ListNode(val);ListNode cur = head;for (int i = 0; i < index; ++i) {cur = cur.next;}addNode.next = cur.next;cur.next = addNode;++size;//别忘了}public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}// ListNode dummyHead = new ListNode(-1, head);// ListNode cur = dummyHead;ListNode cur = head;for (int i = 0; i < index; ++i) {cur = cur.next;}cur.next = cur.next.next;--size;}
}

这题有点闲麻烦，就不用C++再写一遍了。。。

3.T206：反转链表

T：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

S：

如果再定义一个新的链表，实现链表元素的反转，这是对内存空间的浪费。

其实只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表。

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

3. 接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

4. 最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点。

C++：

    ListNode* reverseList(ListNode* head) {// ListNode* cur = head, pre = NULL;//这样写会导致pre类型错误（ListNode pre）ListNode* cur = head;ListNode* pre = NULL;ListNode* temp = NULL;while (cur != NULL) {temp = cur->next;cur->next = pre;//先反转pre和cur再更新pre = cur;cur = temp;}return pre;}

Java：

    //自己看了Carl的双指针思路后复现public ListNode reverseList(ListNode head) {ListNode cur = head, pre = null;ListNode temp = null;while (cur != null) {temp = cur.next;cur.next = pre;//先反转pre和cur再更新pre = cur;cur = temp;// cur.next = pre;//写这里就会超出时间限制，不知为何。。。}return pre;//返回新链表的头节点即可}

还剩下一个不解之谜，就是不知道为什么一定要先反转pre和cur再更新，否则就会超出时间限制...