1. 实现单链表的插入和删除

#include <iostream>struct ListNode
{explicit ListNode(int val_p = 0, ListNode *next_p = nullptr): next(next_p), val(val_p){}ListNode *next;int val;
};// 添加val节点
void push_val(ListNode **phead, int val)
{if (*phead == nullptr) {std::cout << "phead has been set\n";*phead = new ListNode(val);return;}// 找到尾结点ListNode *tail = *phead;while (tail->next != nullptr) {tail = tail->next;}auto newNode = new ListNode(val);tail->next = newNode;
}// 删除第一个匹配val的节点
void erase_val(ListNode **phead, int val)
{if (*phead == nullptr) {std::cout << "phead is empty\n";return;}ListNode *cur = *phead, *prev = nullptr;if (cur->val == val) {std::cout << "head has changed\n";*phead = cur->next;delete cur;return;}while (cur) {if (cur->val == val) {if(!prev)	return;			// 虽然prev不会为空, 这里主要是为了去除编译器的warningprev->next = cur->next;delete cur;return;}prev = cur;cur = cur->next;}std::cout << "has no value equal to val\n";
}void print_list(ListNode *phead)
{if (phead == nullptr) {std::cout << "phead is empty\n";return;}while (phead) {std::cout << phead->val << ' ';phead = phead->next;}std::cout << '\n';
}void delete_list(ListNode **phead)
{ListNode *cur = *phead;if (cur == nullptr) {std::cout << "phead is empty, do nothing\n";return;}while (cur) {ListNode *next = cur->next;std::cout << cur->val << ' ';delete cur;cur = next;}std::cout << '\n';
}int main()
{ListNode *list = nullptr;push_val(&list, 1);push_val(&list, 2);push_val(&list, 3);push_val(&list, 4);erase_val(&list, 4);
//	erase_val(&list, 3);
//	erase_val(&list, 1);
//	erase_val(&list, 2);print_list(list);std::cout << "delete: ";delete_list(&list);return 0;
}

2. 从尾到头打印链表

LCR 123. 图书整理 I - 力扣（LeetCode）

2.1 题目描述

给你一个单链表的头结点，从尾到头打印出链表的每个节点的值。

示例 1：

输入：head = [3,6,4,1]
输出：[1,4,6,3]

2.2 方法1，直接逆转

class Solution {    vector<int> v;
public:vector<int> reverseBookList(ListNode* head) {if(head == nullptr)    return {};reverseList(head);while(head) {int val = head->val;std::cout << val;v.push_back(val);head = head->next;}return v;}// 链表逆置void reverseList(ListNode* &head){ListNode* prev = nullptr, *cur= head, *next = cur->next;// 只有一个节点, 不需要逆置, 直接返回if(next == nullptr)return;while(next) {auto next_next = next->next;        // 先保存一下next->next = cur;cur->next = prev;prev = cur;cur = next;next = next_next;}head = cur;    // 把head归位}
};

有可能要求不能修改链表的结构，这样就用到了下面两种方法

2.3 方法2，使用栈

class Solution {std::stack<int> s;
public:vector<int> reverseBookList(ListNode* head) {vector<int> v;while(head) {s.push(head->val);head = head->next;}while(!s.empty()) {int val = s.top();v.push_back(val);std::cout << val << ' ';s.pop();}return v;}
};

方法3，递归

class Solution {    vector<int> v;
public:vector<int> reverseBookList(ListNode* head) {dfs(head);return v;}void dfs(ListNode* cur){if(cur == nullptr) {return;}dfs(cur->next);std::cout << cur->val;v.push_back(cur->val);}
};