Day3
1.语法不熟悉，得多练习，反复写
2.虚拟头结点的使用可以让代码更加简洁
203.移除链表元素
头结点的删除和其他节点的删除不一样：删除其他节点，都需要更新其前一个节点的指针，删除头结点，只用把head指针指向下一个节点。所以写代码要分为删除头结点和删除非头结点来写。
有没有一个办法让所有节点的删除方式相同？虚拟头节点
直接删除
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {//删除头结点while(head != NULL && head -> val == val){ListNode* tmp = head;head = head -> next;delete tmp;}//删除非头结点ListNode *cur = head;while(cur != NULL && cur -> next != NULL){if(cur -> next -> val == val){ListNode* tmp = cur -> next;cur -> next = cur -> next -> next;delete tmp;}else{cur = cur -> next;}}return head;}
};
使用虚拟头结点
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {//创建虚拟头结点ListNode* dummyHead = new ListNode(0);dummyHead -> next = head;ListNode* cur = dummyHead; while(cur != NULL && cur -> next != NULL){if(cur -> next -> val == val){ListNode *tmp = cur -> next;cur -> next = cur -> next -> next;delete tmp;}else{cur = cur -> next;}}head = dummyHead -> next;delete dummyHead; //记得回收空间，第一次写忘掉了return head;}
};
707.设计链表
addAtIndex方法的描述不太好理解，如下举例说明：
假设初始链表为 [1, 2, 3]：
情况 1：index = 1, val = 5
-
新节点
5插入到下标1的位置之前，原链表的第 1 个节点是2。 -
插入后链表变为
[1, 5, 2, 3]。
情况 2：index = 3, val = 7
-
插入后链表变为
[1, 2, 3, 7]。
情况 3：index = 5, val = 9
-
链表长度为
3，index = 5超过了长度，不进行任何插入操作，链表保持[1, 2, 3]。
情况 4：index = 0, val = 4
-
下标
0是链表的开头位置，新节点4会成为新的头节点。 -
插入后链表变为
[4, 1, 2, 3]。
class MyLinkedList {
public://定义链表节点结构体struct LinkedNode{int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}//nullptr是C++中的关键字，表示空指针};//初始化MyLinkedList对象MyLinkedList() {_dummyHead = new LinkedNode(0); //虚拟头结点_size = 0;}//获取第index个节点的值，无效则返回-1，节点从0开始int get(int index) {if(index > (_size-1) || index < 0) return -1;LinkedNode* cur = _dummyHead -> next;while(index--){cur = cur -> next;}return cur -> val;}//头插法void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode -> next = _dummyHead -> next;_dummyHead -> next = newNode;_size ++;}//尾插法void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(cur -> next != nullptr){cur = cur -> next;}cur -> next = newNode;_size ++;}void addAtIndex(int index, int val) {if(index > _size) return;if(index < 0) index = 0;//把index小于0的情况也看作头插法LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(index --){cur = cur -> next;}newNode -> next = cur -> next;cur -> next = newNode;_size++;}void deleteAtIndex(int index) {if(index > _size - 1 || index < 0) return;LinkedNode *cur = _dummyHead;while(index --){cur = cur -> next;}LinkedNode *temp = cur -> next;cur -> next = cur -> next -> next;delete temp;_size --;}
void printLinkedList(){LinkedNode* cur = _dummyHead;while(cur -> next != nullptr){cout << cur->next ->val << " ";cur = cur -> next;}cout << endl;}
private:int _size;LinkedNode* _dummyHead;
};
206.反转链表
双指针法：
网站上的动图很形象。
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre = NULL;ListNode* cur = head;ListNode* tmp;while(cur != NULL){tmp = cur -> next;cur -> next = pre;pre = cur;cur = tmp;}return pre;}
};
递归写法：
class Solution {
public:ListNode* reverse(ListNode* cur, ListNode* pre) {//递归终止的条件if(cur == NULL) return pre;ListNode* tmp = cur -> next;cur -> next = pre;return reverse(tmp, cur);}ListNode* reverseList(ListNode* head) {return reverse(head, NULL);}
};