代码随想录算法训练营第三天|LeetCode203,707,206
LeetCode 203 移除链表元素
题目链接:https://leetcode.cn/problems/remove-linked-list-elements/description/
//区分了删除头结点元素和删除非头结点元素
/**
* 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) {
//删除头结点元素
//注意不能用if,如果前面的结点元素都和val相等只能删掉一个
//if(head != NULL && head->val == val){
while(head != NULL && head->val == val){
ListNode *tmp = head;
head = head->next;
delete tmp;
}
//删除非头结点元素
ListNode *ptr = head;
while(ptr != NULL && ptr->next != NULL){
if(ptr->next->val == val){
ListNode *tmp = ptr->next;
ptr->next = ptr->next->next;
delete tmp;
}
else{
ptr = ptr->next;
}
}
return head;
}
};
//使用虚拟头结点遍历,就无需区分头结点和非头结点
/**
* 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) {
//设置一个虚拟头结点,并将其初始化
ListNode *virtualNode = new ListNode(0);
virtualNode->next = head;
ListNode *virtualHead = virtualNode;
//循环判断
while(virtualNode->next != NULL){
if(virtualNode->next->val == val){
ListNode *tmp = virtualNode->next;
virtualNode->next = virtualNode->next->next;
delete tmp;
}
else{
virtualNode = virtualNode->next;
}
}
return virtualHead->next;
}
};
视频讲解链接:https://www.bilibili.com/video/BV18B4y1s7R9/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d
文章讲解链接:https://programmercarl.com/0203.移除链表元素.html#其他语言版本
LeetCode 707 设计链表
题目链接:https://leetcode.cn/problems/design-linked-list/description/
class MyLinkedList {
public:
struct ListNode{
int _val; //该节点存储的值
ListNode *_next; //指向下一个节点的指针
//节点构造函数
ListNode (int val)
:_val(val)
,_next(nullptr)
{
//cout << "ListNode(int)" << endl;
}
};
//初始化链表
MyLinkedList() {
//ListNode _virtualHead(0);
_virtualHead = new ListNode(0); //初始化一个虚拟头结点
_size = 0; //链表初始长度为0
}
int get(int index) {
//边界判断
if((index > _size - 1) || index < 0){
return -1;
}
ListNode *ptr = _virtualHead;
for(int i = 0; i <= index; i++){
ptr = ptr->_next;
}
return ptr->_val;
}
void addAtHead(int val) {
ListNode *newNode = new ListNode(val);
newNode->_next = _virtualHead->_next;
_virtualHead->_next = newNode;
_size++;
//cout << _virtualHead->_next->_val;
}
void addAtTail(int val) {
ListNode *newNode = new ListNode(val);
ListNode *ptr = _virtualHead;
while(ptr->_next != NULL) ptr = ptr->_next;
ptr->_next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if(index < _size && index > 0){
ListNode *ptr = _virtualHead;
for(int i = 0; i < index; i++) ptr = ptr->_next;
ListNode *newNode = new ListNode(val);
newNode->_next = ptr->_next;
ptr->_next = newNode;
_size++;
}
else if(index <= 0){
addAtHead(val);
}
else if(index == _size){
addAtTail(val);
}
}
void deleteAtIndex(int index) {
if(index < _size && index >= 0){
ListNode *ptr = _virtualHead;
for(int i = 0; i < index; i++) ptr = ptr->_next;
ListNode *tmp = ptr->_next;
ptr->_next = tmp->_next;
delete tmp;
--_size;
}
}
// 打印链表
void printLinkedList() {
ListNode* ptr = _virtualHead;
while (ptr->_next != nullptr) {
cout << ptr->_next->_val << " ";
ptr = ptr->_next;
}
cout << endl;
}
//数据成员
private:
ListNode *_virtualHead;
int _size;
};
视频讲解链接:https://www.bilibili.com/video/BV1FU4y1X7WD/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d
文章讲解链接:https://programmercarl.com/0707.设计链表.html#代码
LeetCode 206 反转链表
题目链接:https://leetcode.cn/problems/reverse-linked-list/description/
/**
* 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* reverseList(ListNode* head) {
//利用双指针
ListNode *pre = NULL;
ListNode *ptr = head;
//利用tmp保存下一个节点
ListNode *tmp;
while(ptr){
tmp = ptr->next; //保存下一个节点
ptr->next = pre; //进行翻转操作
pre = ptr;
ptr = tmp;
}
return pre;
}
};