02链表
注意，下面代码中涉及到的ListNode，其定义如下：
c++/** * 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) {} * }; */
移除链表元素
题目
链接：https://leetcode.cn/problems/remove-linked-list-elements/description/
给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。示例 1：
c++输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]示例 2：
c++输入：head = [], val = 1 输出：[]示例 3：
c++输入：head = [7,7,7,7], val = 7 输出：[]提示：
- 列表中的节点数目在范围
[0, 104]内1 <= Node.val <= 500 <= val <= 50
题解
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode h(0, head);
ListNode* p = &h;
while(p){
if(p->next != nullptr && p->next->val == val) p->next = p->next->next;
if(p->next == nullptr || p->next->val != val) p = p->next;
}
return h.next;
}
};本题思路：构造虚拟头节点，方便删除操作。
设计链表
题目
链接：https://leetcode.cn/problems/design-linked-list/description/
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：
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的节点。示例：
c++输入 ["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。
题解
class MyLinkedList {
public:
MyLinkedList() {
this->size = 0;
this->head = new ListNode(0);
}
int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode *cur = head;
for (int i = 0; i <= index; i++) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
addAtIndex(0, val);
}
void addAtTail(int val) {
addAtIndex(size, val);
}
void addAtIndex(int index, int val) {
if (index > size) {
return;
}
index = max(0, index);
size++;
ListNode *pred = head;
for (int i = 0; i < index; i++) {
pred = pred->next;
}
ListNode *toAdd = new ListNode(val);
toAdd->next = pred->next;
pred->next = toAdd;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
ListNode *pred = head;
for (int i = 0; i < index; i++) {
pred = pred->next;
}
ListNode *p = pred->next;
pred->next = pred->next->next;
delete p;
}
private:
int size;
ListNode *head;
};本题思路：本题题解为官方题解，注意构造虚拟节点。
反转链表
题目
链接：https://leetcode.cn/problems/reverse-linked-list/description/
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
c++输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：
c++输入：head = [1,2] 输出：[2,1]示例 3：
c++输入：head = [] 输出：[]提示：
- 链表中节点的数目范围是
[0, 5000]-5000 <= Node.val <= 5000**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
题解
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* p = head;
while(p){
ListNode* next = p->next;
p->next = pre;
pre = p;
p = next;
}
return pre;
}
};本题思路：采用头插法逆置链表。
两两交换链表中的节点
题目
链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]示例 2：
输入：head = [] 输出：[]示例 3：
输入：head = [1] 输出：[1]提示：
- 链表中节点的数目在范围
[0, 100]内0 <= Node.val <= 100
题解
/**
* 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* swapPairs(ListNode* head) {
ListNode h(0, head);
ListNode* p = &h;
while(p){
ListNode *q = p->next, *u = nullptr;
if(q) u = q->next;
if(u){
//只有后面有两个元素才有交换元素的必要
q->next = u->next;
p->next = u;
u->next = q;
p = q;
}else{
p = nullptr;
}
}
return h.next;
}
};本题思路：注意链表两个两个地遍历。
删除链表的倒数第N个节点
题目
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]示例 2：
输入：head = [1], n = 1 输出：[]示例 3：
输入：head = [1,2], n = 1 输出：[1]提示：
- 链表中结点的数目为
sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz**进阶：**你能尝试使用一趟扫描实现吗？
题解
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode h(0, head); //构造虚拟头节点
ListNode *p = &h, *q = &h;
int cnt = 0;
while(cnt < n) p = p->next, cnt++;
while(p->next) {
p = p->next;
q = q->next;
}
q->next = q->next->next;
return h.next;
}
};本题思路：本题采用双指针的方式，前面的指针先走n步，后面的指针再跟着走，当前面的指针到达结尾时，后面的指针即为目标位置。
链表相交
题目
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。图示两个链表在节点
c1开始相交**：**
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。提示：
listA中节点数目为mlistB中节点数目为n0 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0- 如果
listA和listB有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]**进阶：**你能否设计一个时间复杂度
O(n)、仅用O(1)内存的解决方案？
题解
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA, *p2 = headB;
//相当于把A部分+B部分+公共部分走了一遍，如果走完了没有找到公共的，一定会一同走向null，故返回null
while (p1 != p2) {
p1 = p1 ? p1->next : headB;
p2 = p2 ? p2->next : headA;
}
return p1;
}
};本题思路：
当p1(初始指向A链表)走到头，指向B链表头开始走；当p2((初始指向B链表))走到头，指向A链表头开始走。分两种情况：
① 如果存在相交节点且A、B自有部分长度相同，当自有部分走完，自然找到相交节点
② 如果存在相交节点且A、B自有部分长度不同，在相交节点前p1和p2都走过了A自有部分+AB公共部分+B自有部分，此段长度相同
③如果不存在相交节点，p1和p2走完A链表+B链表，此段长度相同，会同时指向
nullptr
环形链表II
题目
链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。提示：
- 链表中节点的数目范围在范围
[0, 104]内-105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引**进阶：**你是否可以使用
O(1)空间解决此题？
题解
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == nullptr) return nullptr;
ListNode *l = head, *h = head;
l = l->next;
h = h->next;
if(h) h = h->next;
else return nullptr;
while(h != nullptr && l != h){
l = l->next;
h = h->next;
if(h) h = h->next;
}
if(!h) return nullptr;
l = head;
while(l != h){
l = l->next;
h = h->next;
}
return h;
}
};本题思路：本题的处理主要是要知道从快慢指针相遇点和链表首元节点一起走，会在环入口相遇。
推导：
fast 和 low 相遇时high指针已经走完了环的 n 圈，因此它走过的总距离为
;
; 也就是说从首元节点出发，到环入口的距离等于相遇点到环的距离加上n个整环的距离。
