1.list容器
2.关于链表，你该了解这些！
3.C++ list（STL list）容器完全攻略
解题思路：
以链表 1 4 2 4 来举例，移除元素4。
但是如果删除的是头节点，移除头结点和移除其他节点的 *** 作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点，因此需要用新的方法：
给链表添加一个虚拟头结点为新的头结点，移除这个旧头结点元素1。
在C++中还要从内存中删除移除后的节点
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0); // 定义一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head 也可以写成:ListNode* dummyHead = new ListNode(0,head)
ListNode* cur = dummyHead; // 定义一个新的指针，指向虚拟头节点
while (cur->next != NULL) { // 指针的下一个节点不为空
if (cur->next->val == val) { // 当指针的下一个节点的值等于目标值
ListNode* tmp = cur->next;
cur->next = cur->next->next; // 指针指向下下个值
delete tmp; // 删除 cur->next
}
else {
cur = cur->next; // 指针向后移动遍历指针
}
}
head = dummyHead->next; // 重新定义头节点
delete dummyHead; // 对虚拟头节点进的空间进行释放，防止内存泄漏
return head;
}
};
要将头结点向后移动一位
将原头结点从内存中删掉
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 删除头结点
while (head != NULL && head->val == val) { // 注意这里不是if
ListNode* tmp = head;
head = head->next;
delete tmp;
}
// 删除非头结点
ListNode* cur = head;
while (cur != NULL && cur->next != NULL) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else {
cur = cur->next;
}
}
return head;
}
};
评论区大佬给出了五种解法：移除链表元素(五种方法)
这里再记录一种双指针法，这位up也讲解的非常清晰：203.移除链表元素
解题思路：
起始这一题看着很长，但主要还是那几行代码的堆叠，只要把那几行代码理解了就不难
以addAtIndex(index,val)为例：
假设链表为1->3->5->7->9，现在要在第2个节点之前插入一个新节点(addAtIndex(2,4))
那么首先新定义一个节点并赋值，然后将定义虚拟头节点指针
然后开始遍历index之前的链表:
然后执行newNode->next = cur->next;
执行cur->next = newNode;size++;
其他几种和这个也是差不多的
class MyLinkedList {
public:
// 定义链表节点结构体
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val) :val(val), next(nullptr) {} //构造函数
};
// 初始化链表
MyLinkedList() {
dummyHead = new LinkedNode(0); //定义虚拟头结点
size = 0; //链表长度
}
// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
int get(int index) {
if (index > (size - 1) || index < 0) { //输入的index不在范围内 等同于>= size
return -1;
}
LinkedNode* cur = dummyHead->next; //当前指针指向真正头节点
while (index--) { //遍历index前面的链表，这里理解不了可以将示例代入
cur = cur->next;
}
return cur->val;
}
// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val); //新建节点并赋值
newNode->next = dummyHead->next; //将虚拟头节点的指向赋值给新建节点的指向(即使新建节点的指向与虚拟头节点相同)
dummyHead->next = newNode; //将虚拟头节点指向新建节点
size++;
}
// 在链表最后面添加一个节点
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = dummyHead;
while (cur->next != nullptr) { //遍历链表到最后位置
cur = cur->next;
}
cur->next = newNode; //链表最后面添加一个节点
size++;
}
//在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
//如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
//如果index大于链表的长度，则返回空
//void addAtIndex(int index, int val) {
// if (index <= 0) {
// addAtHead(val);
// }
// else if (index == size) {
// addAtTail(val);
// }
// else if (index > size) {
// return;
// }
// else {
// LinkedNode* newNode = new LinkedNode(val);
// LinkedNode* cur = dummyHead;
// while (index--) {
// cur = cur->next;
// }
// newNode->next = cur->next;
// cur->next = newNode;
// size++;
// }
//}
void addAtIndex(int index, int val) {
if (index > size) { //大于链表长度返回空
return;
}
LinkedNode* newNode = new LinkedNode(val); //包含了等于链表长度的情况
LinkedNode* cur = dummyHead;
while (index--) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
size++;
}
// 删除第index个节点，如果index 大于等于链表的长度，直接return
void deleteAtIndex(int index) {
if (index >= size || index < 0) {
return;
}
LinkedNode* cur = dummyHead;
while (index--) {
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
size--;
}
// 打印链表
void printLinkedList() {
LinkedNode* cur = dummyHead;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
int size;
LinkedNode* dummyHead;
};
class ListsNode
{
public:
int val;
ListsNode* next;
ListsNode* pre;
ListsNode(int v, ListsNode* n, ListsNode* p):val(v),next(n),pre(p){}
};
class MyLinkedList {
public:
ListsNode* root;
ListsNode* trail;
int size;
/** Initialize your data structure here. */
MyLinkedList() {
root=nullptr;
trail=nullptr;
size=0;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
int temp=0;
ListsNode* cur=root;
while(cur!=nullptr)
{
if(temp==index)
{
return cur->val;
}
cur=cur->next;
temp++;
}
return -1;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
if(root!=nullptr)
{
ListsNode* newNode=new ListsNode(val, root, nullptr);
root->pre=newNode;
root=newNode;
}
else
{
root=new ListsNode(val, nullptr,nullptr);
trail=root;
}
size++;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
if(trail!=nullptr)
{
ListsNode* newNode = new ListsNode(val, nullptr, trail);
trail->next=newNode;
trail=newNode;
}
else
{
trail=new ListsNode(val, nullptr, nullptr);
root=trail;
}
size++;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
if(index<=0)
{
addAtHead(val);
return;
}
if(index==size)
{
addAtTail(val);
return;
}
int temp=0;
ListsNode* pre=nullptr;
ListsNode* cur=root;
while(cur!=nullptr)
{
if(temp==index)
{
ListsNode* newNode=new ListsNode(val, cur, pre);
if(pre!=nullptr)
{
pre->next=newNode;
}
cur->pre=newNode;
size++;
return;
}
pre=cur;
cur=cur->next;
temp++;
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
int temp=0;
ListsNode* pre=nullptr;
ListsNode* cur=root;
if(index==0)
{
ListsNode* old=root;
root=root->next;
if(root!=nullptr)
{
root->pre=nullptr;
}
delete old;
size--;
return;
}
if(index==size-1)
{
ListsNode* old=trail;
trail=trail->pre;
if(trail!=nullptr)
{
trail->next=nullptr;
}
delete old;
size--;
return ;
}
while(cur!=nullptr)
{
if(temp==index)
{
ListsNode* old=cur;
if(pre!=nullptr)
{
pre->next=cur->next;
}
if(cur->next!=nullptr)
{
cur->next->pre=pre;
}
delete old;
size--;
return;
}
pre=cur;
cur=cur->next;
temp++;
}
}
};
解题思路：
只需要将链表的next指针的指向翻转
定义两个指针，cur指针指向头节点、pre指针指向null空指针；
然后将cur->next指向pre，移动两个指针；
当cur指向null，翻转结束。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp; // 保存cur的下一个节点
ListNode* cur = head; // cur指针指向头节点
ListNode* pre = NULL; // pre指针指向null
while (cur) { // 遍历链表
temp = cur->next; // 保存cur的下一个节点，因为接下来要改变cur->next
cur->next = pre; // 翻转 *** 作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
};
和双指针法的思路差不多
class Solution {
public:
ListNode* reverse(ListNode* pre, ListNode* cur) {
if (cur == NULL) return pre;
ListNode* temp = cur->next;
cur->next = pre;
// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
// pre = cur;
// cur = temp;
return reverse(cur, temp);
}
ListNode* reverseList(ListNode* head) {
// 和双指针法初始化是一样的逻辑
// ListNode* cur = head;
// ListNode* pre = NULL;
return reverse(NULL, head);
}
};
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）