LeetCode-链表问题
1.移除链表元素 1. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
这次删除的是链表，链表删除元素比较方便，但要注意元素边界
思路： 先提出剔除 链表前部分符合条件元素，找真正的起点
从起点开开始遍历，查看下一个元素是否符合，符合跳过，更改指针方向
ListNode *removeElements(ListNode *head, int val) {
while (head->next != nullptr && head->val == val) { //看前部分是否符合条件
head = head->next;
}
ListNode *cur = head; //真正的head， 用cur去操作，head是我们要的结果
while (cur != nullptr && head->next != nullptr) {
if (cur->next->val == val) { //如果符合 跳过指向下下个
cur->next = cur->next->next;
} else {
cur = cur->next; //不符合，直接下一个i
}
return head; //返回的是head，cur 是用来操作链表的
}
}
2. 反转链表 2\. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表 (经典题目了)
思路1： 建一个虚拟的头节点，然后遍历链表，改变元素指针指向（指向虚拟节点）
思路2： 用栈的特性，遍历链表入栈，出栈一个一个链接起来
ListNode *reverseList(ListNode *head) {
ListNode * vhead = nullptr;
ListNode *cur = nullptr;
while (head != nullptr) //遍历链表
{
cur = head; //cur 指向当前元素
head = head ->next; // head 指向下一个元素，为下一次遍历做准备
cur->next = vhead; // 当前元素指向虚拟节点
vhead = cur; //更新虚拟节点的位置，保证下次 元素指向的还是头节点
}
return vhead; // 遍历结束 最后 执行代码是 vhead = cur; 所以vhead执行最后一个也是反转后第一个
}
3. 两两交换链表中的节点 3\. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路： 因为两两交换，所以每次都选两个节点，开始的时候用一个虚拟的节点作为头结点
ListNode* swapPairs(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
ListNode *dyHead = new ListNode(0);
dyHead->next = head;
ListNode *cur = dyHead; //到了这里 cur和dyhead控制着的相同的节点，并且该节点指向链表头部
// 下个节点和 下下个节点是否存在
while (cur->next && cur->next->next) {
ListNode *t1 = cur->next; //下个节点 t1 对应 a
ListNode *t2 =cur->next->next; //下下个节点 t2 对应 b
//改变节点指向 如下图所示
t1->next = t2->next; //3
t2->next = t1; // 2
cur->next= t2; // 1
cur = cur->next->next; //为下次交换节点做为准备
}
return dyHead->next;
}
4.链表相交 4.链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
!img
思路： A 和 B 都同时走
若相交，链表A： a+c, 链表B : b+c
a+c+b+c = b+c+a+c 。则会在公共处c起点相遇。
若不相交，a+b = b+a 。因此相遇处是NULL
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *fast = headA;
ListNode *slow = headB;
while (fast != slow) {
fast = (fast != nullptr ? fast->next : headB);
slow = (slow != nullptr ? slow->next : headA);
}
return fast;
}
5. 反转链表 II 5\. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
!img
反转链表升级版
思路： 遍历链表到到 left的位置 以left 上一个节点为头结点，接下来遍历节点，以头插法的方式插入头结点上（此时问题 又转换到而来 反转链表 I 的问题，不同的是并不是遍历到尾）
ListNode *reverseBetween(ListNode *head, int left, int right) {
if(head->next == nullptr)
return head;
ListNode *vHead = new ListNode(0);
vHead ->next = head;
ListNode *p = vHead;
ListNode *q = vHead->next;
// 第一次for 循环走到 定位到 left 的位置，p和q
for (int i = 0; i < left-1; i++) {
p = p->next;
q = q->next;
}
// 第二次 for 开始反转需要的节点
for (int i = 0; i < right - left; i++) {
//保留下一个节点
ListNode *temp = q->next;
// 为下一个反转做好准备
q->next = q->next->next;
// 头插法，查到 p 的后面
temp->next = p->next;
// 更新 p的位置 ，为 p做好准备
p->next = temp;
}
return vHead->next;
}
K 个一组翻转链表 K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
思路： 每k个节点反转， 可以把问题拆分到 每组 k个节点的反转，最后将每组拼接起来，对于反转 一个链表比较容易，这次反转有指定得的范围，k个几点
利用递归可以将每组拼接起来
class Solution {
public:
//反转 k个节点的链表
ListNode* reverseList(ListNode* head,ListNode* tail) {
ListNode *vhead = new ListNode();
ListNode *v = vhead->next;
while(head != tail){
ListNode *t = head->next;
head->next = v;
v = head;
head = t;
}
return v;
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *node = head;
//遍历k个节点
for(int i = 0;i < k; i++){
if(node == nullptr)
return head;
node = node->next;
}
// 传入首尾节点
ListNode *res = reverseList(head,node);
// 递归 此时head已经是尾节点
head->next =reverseKGroup(node,k);
return res;
}
};