目录
题目链接：203. 移除链表元素-简单
题目描述：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
- 列表中的节点数目在范围
[0, 10^4]内 1 <= Node.val <= 500 <= val <= 50
设置一个虚拟头结点在进行移除节点操作
代码如下：
//时间复杂度：O(n)
//空间复杂度：O(1)
/**
* 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* vhead = new ListNode(-1);
vhead -> next = head;
ListNode* cur = vhead;
while(cur && cur->next)
{
if(cur->next->val == val)
{
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
}
else
cur = cur->next;
}
return vhead->next;
}
};
题目链接：707. 设计链表-中等
题目描述：
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
示例：
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]
解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3
提示：
0 <= index, val <= 1000- 请不要使用内置的 LinkedList 库。
- 调用
get、addAtHead、addAtTail、addAtIndex和deleteAtIndex的次数不超过2000。
代码如下：
//时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
//空间复杂度: O(n)
class MyLinkedList {
public:
struct node{
int val;
node* next;
node(int val):val(val), next(nullptr){}
};
MyLinkedList() {
vnode = new node(0);
len = 0;
}
int get(int index) {
if(index >= len || index < 0)
return -1;
node* cur = vnode->next;
while(index--)
{
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
node* newnode = new node(val);
newnode->next = vnode->next;
vnode->next = newnode;
++len;
}
void addAtTail(int val) {
node* cur = vnode;
while(cur->next)
{
cur = cur->next;
}
node* newnode = new node(val);
cur->next = newnode;
++len;
}
void addAtIndex(int index, int val) {
if(index > len || index < 0)
return;
else if(index == len)
{
addAtTail(val);
}
else
{
node* cur = vnode;
while(index--)
{
cur = cur->next;
}
node* newnode = new node(val);
newnode->next = cur->next;
cur->next= newnode;
++len;
}
}
void deleteAtIndex(int index) {
if(index >= len || index < 0)
return;
node* cur = vnode;
while(index--)
{
cur = cur->next;
}
node* temp = cur->next;
cur->next = cur->next->next;
delete temp;
temp = nullptr;
--len;
}
private:
int len;
node* vnode;
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
题目链接：206. 反转链表-简单
题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
方法一：双指针法（三指针法）
过程需要用到一个前指针pre，一个暂存后指针的temp(cur)，还有时刻移动的head指针。核心思路是pre与head建立连接，temp保存head的下一位，pre与head均移动至对应下一位，继续建立连接直至结束。步骤：
pre指针初始化为NULL，代表反向链表最后一个节点的下一位为NULL，temp指针初始化为head节点的后一位- 将
temp指针指向head节点的后一位，否则head节点与它的后一位断开之后就找不到了 - 断开
head节点与head节点后一位的连接，head节点的后一位指向pre节点，这样一来就分为以head节点为头节点的反向链表以及以temp节点为头指针的顺序链表 - 将
pre指针指向head节点，head指针指向temp节点，继续给pre节点与head节点建立反向连接 - 最后，
pre指针指向原链表的最后一个节点，即为新的head节点；原head指针随着移动指向了原链表最后一个节点的下一位，即为NULL，因此，返回pre节点即可
代码如下：
// 时间复杂度：O(n)
// 空间复杂度：O(1)
/**
* 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* temp;
while(head)
{
temp = head->next; // temp指向head的下一位
head->next = pre; // head与pre建立连接
pre = head; // 移动pre
head = temp; // 移动head
}
return pre;
}
};
方法二：递归法，跟双指针法一一对应
代码如下：
// 时间复杂度: O(n), 要递归处理链表的每个节点
// 空间复杂度: O(n), 递归调用了 n 层栈空间
/**
* 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* reverse(ListNode* head, ListNode* pre){
if(head == NULL)
{
return pre;
}
ListNode* temp = head->next;
head->next = pre;
return reverse(temp, head);
}
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
return reverse(head, pre);
}
};