203.移除链表元素
稀里糊涂得连删除链表元素都不会了，看了视频才明白一些
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
while((head!=nullptr) && (head->val == val)){
head = head->next;
}
ListNode* cur = head;
while((cur!= nullptr)&&(cur->next != nullptr)){
if(cur->next->val == val){
cur->next = cur->next->next;
}
else{
cur = cur->next;
}
}
return head;
}
};
每次做链表题的时候，都想不起来创建一个虚拟头结点。看过视频后，办抄半写的自己弄了一份。 关于为什么”ListNode* cur = dummy;”，是因为如果链表是a-b-c，如果我们要删除b,那我们就需要让a->next指向c。如果我们把cur设置为dummy->next，就相当于我们的cur一上来直接就是b，就无法用a和c相连了。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(-1, head);
ListNode* cur = dummy;
while(cur->next != nullptr){
if(cur->next->val == val){
cur->next = cur->next->next;
}
else
{
cur = cur->next;
}
}
return dummy->next;
}
};
707.设计链表
照着Carl的文字解析，跌跌撞撞的手写出了链表。对于边界的问题，掌握得还是很浅，需要多练习。
class MyLinkedList {
public:
struct ListNode{
int val;
ListNode *next;
ListNode(): val(0),next(nullptr){}
ListNode(int x):val(x),next(nullptr){}
ListNode(int x, ListNode *next):val(x),next(next){}
};
MyLinkedList() {
_dummynode = new ListNode(-1);
_size = 0;
}
int get(int index) {
if((index > _size-1) || (index < 0)){
return -1;
}
ListNode* cur = _dummynode->next;
while(index--){
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
ListNode* newhead = new ListNode(val,_dummynode->next);
_dummynode->next = newhead;
_size++;
}
void addAtTail(int val) {
int loop= _size;
ListNode* cur = _dummynode;
while(loop--){
cur = cur->next;
}
ListNode* newTail = new ListNode(val);
cur->next = newTail;
_size++;
}
void addAtIndex(int index, int val) {
if((index > _size) || (index < 0))
return;
ListNode* cur = _dummynode;
while(index--){
cur = cur->next;
}
ListNode* newNode = new ListNode(val,cur->next);
cur->next = newNode;
_size++;
}
void deleteAtIndex(int index) {
if((index >=_size) || (index < 0))
return;
ListNode* cur = _dummynode;
while(index--){
cur = cur->next;
}
cur->next = cur->next->next;
_size--;
}
private:
ListNode* _dummynode;
int _size;
};
206.反转链表
很投机取巧的遍历了两边linkedlist来反转链表。原本想着再建一个链表，但觉得太费空间了。虽然知道有更好的办法，但是自己还是没想出来。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
vector<int> val_list;
ListNode* cur = head;
while(cur != nullptr){
val_list.push_back(cur->val);
cur=cur->next;
}
cur = head;
for(auto it=val_list.rbegin(); it!=val_list.rend();it++){
cur->val = *it;
cur=cur->next;
}
return head;
}
};
跟着Carl，写出来了双指针版本的答案，相对来说，哪个值赋给谁这个问题还是有点绕。尤其是递归版本的解法更难懂了，还是有点一知半解。以后这道题还要多做几遍。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp;
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur){
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};
