链表1-快慢指针（删除倒数），反转问题

19. 删除链表的倒数第 N 个结点

难度中等1201
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //主要是因为单个元素的情况 所以要新开
        ListNode* dummpy = new ListNode(0, head);
        ListNode* p = dummpy;
        ListNode* q = dummpy;
        int t = n;
        //先遍历到尾部
        while(t --){
            p = p->next;
        }
        while(p->next != nullptr){
            p = p->next;
            q = q->next;
        }
        q->next = q->next->next;
        ListNode* ans = dummpy->next;
        delete dummpy;
        return ans;
    }
};

25. K 个一组翻转链表

难度困难917
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

/**
 * 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:
    //局部翻转
    pair<ListNode*, ListNode*> Reverse(ListNode* head, ListNode* tail){
        ListNode* cur = head;
        ListNode* pre = tail->next;
        while(pre != tail){
            ListNode* next = cur ->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return {tail, head};
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* nhead = new ListNode(-1);
        nhead->next = head;
        ListNode* pre = nhead;
        while(head != nullptr){
            ListNode* tail = pre;
            //检测剩余节点是否满足小于k
            for(int i = 0; i < k; ++ i){
                tail = tail->next;
                if(tail == nullptr){
                    return nhead->next;
                }
            }
            //缝合，整体更新
            ListNode* nex = tail->next;
            //局部翻转
            tie(head, tail) = Reverse(head, tail);
            //拼接 
            pre->next = head;
            tail->next = nex;
            //更新值
            pre = tail;
            head = tail->next;
        }
        return nhead->next;
    }
};

206. 反转链表

难度简单1522
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

/**
 * 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* cur = head;
        ListNode* pre = nullptr;
        while(cur != nullptr){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

92. 反转链表 II

难度中等788
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummpy = new ListNode(-1);//1.这个用一下真的很方便
        dummpy->next = head;
        ListNode* nhead = head;
        ListNode* pre = dummpy;
        int idx = 1;
        //找到反转点
        while(nhead && idx < left){
            pre = nhead;
            nhead = nhead->next;
            idx ++;
        }
        //开始反转
        ListNode* npre = pre;
        ListNode* oleft = nhead;//2.保存反转后的尾节点，省掉很多操作
        ListNode* nbegin = nhead;
        while(nbegin && idx <= right){
            ListNode* nex = nbegin->next;
            nbegin->next = npre;
            npre = nbegin;
            nbegin = nex;
            idx ++;
        }
        oleft->next = nbegin;
        pre->next = npre;
        return dummpy->next;
    }
};