203 移除链表元素

思路

虚链表头
今天复习写得不是很流畅
虚假头结点可以不用考虑原始头结点是否需要删除，这样以一个统一的标准记忆更方便。
没记清楚的点在于：忘记需要再定义一个指针 = dummyhead了
（如果是直接处理原始链表，最后在判断头结点时需要注意空链表的情况）

代码

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 因为可能这个链表的头节点就是需要删除的结点// 所以我们设置一个虚假的头结点// 遍历结束后再删除这个虚假头结点ListNode* dummyhead = new ListNode(0);dummyhead->next = head;ListNode* cur;cur = dummyhead;while (cur->next != NULL) {if (cur->next->val == val) {ListNode * temp;temp = cur->next;cur->next = cur->next->next;delete temp;}else {cur = cur->next;}} head = dummyhead->next;delete dummyhead;return head;}
};

总结

1. 虚拟头结点

707 设计链表

思路

之前自己也就刚写到这题，到这题之后都还没写过了
这道题设计到的链表操作比较多，适合复习链表操作
这题磨了好久……主要是没理解下标从0开始.
实际上 设计的_size变量就是链表长度（可以对标于数组长度）
剩下的一些细节位置问题（比如index--，cur=_dummyhead等问题）死记硬背效果不好，在写的时候画图辅助效果比较好

代码

class MyLinkedList {// 重要：下标从0开始
public:struct  ListNode{int val;ListNode* next;ListNode(int val): val(val),next(nullptr) {}};MyLinkedList() {_dummyhead = new ListNode(0);_size = 0;}int get(int index) {if (index > (_size-1) || index < 0) {return -1;}ListNode* cur;cur = _dummyhead->next;while (index --) {cur = cur->next;}return cur->val;}void addAtHead(int val) {ListNode* node = new ListNode(val);// ListNode* cur;// cur = _dummyhead->next;// _dummyhead -> next = node;// node -> next = cur;node ->next = _dummyhead ->next;_dummyhead -> next = node;_size++;}void addAtTail(int val) {ListNode* node = new ListNode(val);ListNode* cur;cur = _dummyhead;while (cur -> next != NULL) {cur = cur -> next;}cur -> next = node;_size ++;}void addAtIndex(int index, int val) {if (index > _size) {return;}if (index < 0) index = 0;ListNode* node = new ListNode(val);ListNode* cur = _dummyhead;while (index--){cur = cur -> next;}node ->next = cur -> next;cur -> next = node;_size++;}void deleteAtIndex(int index) {if (index <0 || index >= _size){return;}else {ListNode* cur;cur = _dummyhead;while (index --) {cur = cur -> next;}ListNode* tmp;tmp = cur -> next;cur -> next = cur -> next -> next;delete tmp;_size --;}}private:ListNode* _dummyhead;int _size; // 这个_size的含义是链表的长度，==len(数组)
};

总结

1. _size的含义是链表长度，可以理解为数组长度，与数组下标&数组长度的关系一样
2. 可以用于复习链表操作

206 反转链表

思路

定义两个指针，一个cur指向原始头结点，一个pre指向空
在循环过程中，定义临时指针tmp指向cur->next，逆转两个结点关系后，向后遍历。循环条件是cur没到NULL，当cur到NULL时，pre就在原始链表最后一个数组上了，返回pre.

代码

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

总结

1. 比较简单的一题。