Leetcode203
解题思路：此题较为简单，遍历链表，查找到val，跳过即可。
需注意的是，采用了虚拟头结点的方法
程序：
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while(cur->next != NULL){
if(cur->next->val == val){
cur->next = cur->next->next;
}
else{
cur = cur->next;
}
}
return dummyHead->next;
}
};
Leetcode707
思路：此题考察了对链表的全面理解，较为复杂
首先，需要自己定义链表，与以往的核心代码稍有不同，需自己掌握链表的定义方法。
同样的使用了虚拟头结点的方法，需要注意的是，在涉及到对链表的增删操作时，需要使cur指向目标节点的前一节点，否则会出现错误操作，而涉及到读取节点值的操作时，则需要使cur指向目标节点。
程序：
class MyLinkedList {
public:
struct LinkNode{
int val;
LinkNode* next;
LinkNode(int val):val(val), next(nullptr){}
};
int size = 0;
LinkNode* dummyHead = new LinkNode(0);
MyLinkedList() {
}
int get(int index) {
if(index < 0 || index > (size - 1)) return -1;
LinkNode* cur = dummyHead->next;
while(index--) cur = cur->next;
return cur->val;
}
void addAtHead(int val) {
LinkNode* newLink = new LinkNode(val);
newLink->next = dummyHead->next;
dummyHead->next = newLink;
size++;
}
void addAtTail(int val) {
LinkNode* newLink = new LinkNode(val);
LinkNode*cur = dummyHead;
while(cur->next != NULL) cur = cur->next;
cur->next = newLink;
size++;
}
void addAtIndex(int index, int val) {
if(index < 0 || index > size ) return;
LinkNode*cur = dummyHead;
LinkNode* newLink = new LinkNode(val);
while(index--) cur = cur->next;
LinkNode* temp = cur->next;
newLink->next = temp;
cur->next = newLink;
size++;
}
void deleteAtIndex(int index) {
if(index < 0 || index >= size ) return;
LinkNode* cur = dummyHead;
while(index--) cur = cur->next;
LinkNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
size--;
}
};
LeetCode 206
思路：此题可以使用两种方法解题，但思路大同小异。
（1）双指针法
使用两个不同的指针，更换两节点的指向，并对指针进行更新。知道遍历完整个链表
程序：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp;
ListNode* cur = head;
ListNode* pre = NULL;
while(cur != NULL){
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};
（2）迭代法
思路同上，实现的方式有所不同
程序：
classSolution{public:
ListNode*reverse(ListNode* pre,ListNode* cur){
if(cur == NULL) return pre;
ListNode* temp= cur->next;
cur->next = pre;
return reverse(cur,temp);
}
ListNode*reverseList(ListNode* head){
return(reverse(NULL,head));
}
今日总结：
1.在设计链表时注意到了之前已经忘记的细节：增删操作时cur指向目标节点的前一节点。
2.复习了迭代法三部曲，但是感觉迭代法扔掌握的不够牢，需要继续学习。
今日学习 2h
