链表|203.移除链表元素、707.设计链表、206.反转链表
203.移除链表元素
自己审题思路
移除链表元素，需要拿到移除元素的前一个Node地址
看完代码随想录题解后的收获
链表操作，特别是链表删除操作，建立一个虚拟节点指向头结点会很方便(否则需要考虑删除的是否是头结点)。
代码：
/*
struct ListNode {
int val;
ListNode* next;
ListNode(int val) : val(val), next(nullptr) {}
};*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (head == nullptr) return head;
ListNode* dummyNode = new ListNode();
dummyNode->next = head;
ListNode* cur = dummyNode;
while (cur->next) {
if (cur->next->val == val) {
cur->next = cur->next->next;
} else {
cur = cur->next;
}
}
return dummyNode->next;
}
};
参考详解
707.设计链表
自己审题思路
考察具体的链表操作，其中有一些细节需要注意
看完代码随想录题解后的收获
这道题覆盖了链表的常见操作，是练习链表操作非常好的一道题
其中细节比较容易犯错，借着这道题debug了一遍代码，算是为后续代码debug开个头
能够debug的代码：
// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include<iostream>
using namespace std;
// @before-stub-for-debug-end
/*
* @lc app=leetcode.cn id=707 lang=cpp
*
* [707] 设计链表
*/
// @lc code=start
class MyLinkedList {
public:
struct ListNode {
int val;
ListNode* next;
ListNode(int val) : val(val), next(nullptr) {}
ListNode(int val, ListNode* next) : val(val), 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* newNode = new ListNode(val);
ListNode* cur = dummyNode;
cur->next = newNode; //错误写法，没有将newNode->next定义，每次给链表头插入元素之后，之前添加的元素就丢失了
size++;
} */
void addAtHead(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = dummyNode->next;
dummyNode->next = newNode;
size++;
}
void addAtTail(int val) {
ListNode* newNode = new ListNode(val);
ListNode* cur = dummyNode;
int x = size;
while (x--) {// 之前这里使用的size--，错误，不能将size值改变！！！
cur = cur->next;
}
cur->next = newNode;
size++;
}
void addAtIndex(int index, int val) {
if (index > size) return;
if (index < 0) index = 0;
ListNode* newNode = new ListNode(val);
ListNode* cur = dummyNode;
while (index--) {
cur = cur->next;
}
ListNode* temp = cur->next;
cur->next = newNode;
newNode->next = temp;
/* newNode->next = cur->next;
cur->next = newNode; */
size++;
}
void deleteAtIndex(int index) {
if (index >= size || index < 0) return;
ListNode* cur = dummyNode;
ListNode* temp;
while (index--) {
cur = cur->next;
}
temp = cur->next;
cur->next = cur->next->next;
delete temp;
temp = nullptr;
size--;
}
void printLinkedList() {
ListNode* cur = dummyNode;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
system("pause");
}
private:
ListNode* dummyNode;
int size;
};
int main () {
MyLinkedList* myLinkedList = new MyLinkedList();
myLinkedList->addAtHead(1);
myLinkedList->addAtHead(3);
myLinkedList->addAtHead(1);
// myLinkedList->addAtTail(3);
myLinkedList->addAtIndex(3, 0);
myLinkedList->printLinkedList();
myLinkedList->addAtIndex(1, 2);
myLinkedList->printLinkedList();
myLinkedList->get(1);
myLinkedList->printLinkedList();
myLinkedList->deleteAtIndex(1);
myLinkedList->printLinkedList();
cout << myLinkedList->get(1) << endl;
return 0;
}
/* int main () {
MyLinkedList* myLinkedList = new MyLinkedList();
myLinkedList->addAtHead(1);
myLinkedList->addAtTail(3);
myLinkedList->printLinkedList();
myLinkedList->addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList->printLinkedList();
myLinkedList->get(1); // 返回 2
myLinkedList->printLinkedList();
myLinkedList->deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList->printLinkedList();
cout << myLinkedList->get(1) << endl; // 返回 3
return 0;
} */
如果将ListNode* dummyNode定义在结构体struct ListNode之前，在编译时就会出现以下报错：
error: incompatible pointer types assigning to 'ListNode *' from 'MyLinkedList::ListNode *'
new ListNode(-1) 是MyLinkedList::ListNode *类型，而 dummyNode被识别成了ListNode *类型，因为在类MyLinkedList定义struct ListNode之前就定义了 dummyNode。
4070d4cf0f962addb13c89dcdedeb00.png
参考详解
206.反转链表
自己审题思路
经典题，双指针，将后一个节点指向前一个节点
看完代码随想录题解后的收获
利用双指针的思路写出递归版本代码
双指针代码：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur) {
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};
递归版本代码：
class Solution {
public:
ListNode* reverse(ListNode* pre, ListNode*cur) {
if(cur == nullptr) return pre;
ListNode* tmp = cur->next;
cur->next = pre;
return reverse(cur, tmp);
}
ListNode* reverseList(ListNode* head) {
return reverse(nullptr, head);
}
};
参考详解
今日感想：
1、代码隐藏的bug还是需要好好debug看看变量的变化过程；
2、还是要加强C++语法的熟悉。
