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);
}
};