【代码随想录算法训练营——Day3】链表——203.移除链表元素、707.设计链表、206.反转链表

LeetCode题目链接
https://leetcode.cn/problems/remove-linked-list-elements/
https://leetcode.cn/problems/design-linked-list/
https://leetcode.cn/problems/reverse-linked-list/

题解
203.移除链表元素
重要的是创立头结点，这点在写题前已经经受过提示。
注意移除代码中pre结点创建后，在循环中会跟着head往下走，因此要再创建一个cur结点，并令其初值等于pre，而不是直接令其next等于head，因为在遍历过程中移动了next指针，头结点被删除后可能在cur的next里没被改变，因此要直接令其值等于pre，来改变其next。
其他的创建链表代码有借鉴AI的（实在是AI有提示，没办法）。

707.设计链表
借助AI的帮助下写了几行（不是很多），主要是在按下标添加结点时，index长度等于链表长度时调用了addAtTail(val)，这点比较要注意，其他的只是模拟。

206.反转链表
在最后return环节那里，是AI给我提示的（没办法，AI太快了），脑中模拟一下就知道是pre返回，这回完全没看题解，都是凭之前的印象做出的，第一遍刷题真的有用！

代码

//203.移除链表元素
#include <iostream>
#include <vector>
using namespace std;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) {if(head == NULL) return NULL;ListNode* pre = new ListNode;pre->next = head;ListNode* cur = pre;while (head != NULL) {if (head->val == val) {pre->next = head->next;head = head->next;}else {pre = head;head = head->next;}}return cur->next;}
};ListNode* createList(vector<int> nums) {if (nums.size() == 0) return NULL;ListNode *pre = new ListNode;pre->next = NULL;ListNode* cur = pre;for (int i = 0;i < nums.size();i++) {cur->next = new ListNode(nums[i]);cur = cur->next;}cur->next = NULL;return pre->next;
}int main() {Solution s;vector<int> nums = {  };ListNode* head = createList(nums);int val = 1;ListNode* node = head;while (node != NULL) {printf("%d ", node->val);node = node->next;}printf("\n");ListNode* result = s.removeElements(head, val);node = result;while (node != NULL) {printf("%d ", node->val);node = node->next;}return 0;
}

//707.设计链表
#include <iostream>
using namespace std;class MyLinkedList {
public:struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}};;MyLinkedList() {preHead = new ListNode();}int getListLen() {ListNode* head = preHead->next;int len = -1;while (head != NULL) {len++;head = head->next;}return len;}int get(int index) {int len = getListLen();if (index < 0 || index > len) return -1;int num = -1;ListNode* head = preHead->next;while (head != NULL) {num++;if (num == index) {return head->val;}head = head->next;}return -1;}void addAtHead(int val) {ListNode* node = new ListNode(val);node->next = preHead->next;preHead->next = node;}void addAtTail(int val) {ListNode* pre = preHead;ListNode* head = preHead->next;while (head != NULL) {pre = head;head = head->next;}ListNode* node = new ListNode(val);pre->next = node;}void addAtIndex(int index, int val) {int len = getListLen() + 1;if (index > len) return;if (index == len) {addAtTail(val); //妙啊return;}ListNode* pre = preHead;ListNode* head = preHead->next;int num = -1;while (num < index - 1) {num++;pre = head;head = head->next;}ListNode* node = new ListNode(val);node->next = pre->next;pre->next = node;}void deleteAtIndex(int index) {int len = getListLen();if (index < 0 || index > len) return;ListNode* pre = preHead;ListNode* head = preHead->next;int num = 0;while (num < index) {pre = head;head = head->next;num++;}pre->next = head->next;delete head;}
private:ListNode* preHead;
};int main() {MyLinkedList myLinkedList;myLinkedList.addAtHead(1);myLinkedList.addAtTail(3);myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3printf("%d\n", myLinkedList.get(1));              // 返回 2myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3printf("%d\n", myLinkedList.get(1));              // 返回 3return 0;
}

//206.反转链表
#include <iostream>
#include <vector>
using namespace std;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* reverseList(ListNode* head) {if (head == NULL) return NULL;ListNode* pre = NULL;while (head != NULL) {ListNode* tmp = head->next;head->next = pre;pre = head;head = tmp;}return pre;}
};ListNode* createList(vector<int> nums) {if (nums.size() == 0) return NULL;ListNode* pre = new ListNode;pre->next = NULL;ListNode* cur = pre;for (int i = 0;i < nums.size();i++) {cur->next = new ListNode(nums[i]);cur = cur->next;}cur->next = NULL;return pre->next;
}int main() {vector<int> nums = {  };ListNode* head = createList(nums);ListNode* node = head;while (node != NULL) {printf("%d ", node->val);node = node->next;}printf("\n");Solution s;ListNode* result = s.reverseList(head);node = result;while (node != NULL) {printf("%d ", node->val);node = node->next;}return 0;
}