237. 删除链表中的节点

https://leetcode.cn/problems/delete-node-in-a-linked-list/

方法:
记node的下一个节点尾next 要删除node

1.可以把next的数据搬到node,
2.然后释放next节点,让node链接其下一个节点

由于题目已经说了,node不是尾节点,所以node->next->next不会非法访问！

class Solution {
public:
    //题目数据保证需要删除的节点 不是末尾节点
    //无法访问链表的头节点 head ，只能直接访问 要被删除的节点
    void deleteNode(ListNode* node) {
        //node next 要删除node =>可以把next的数据搬到node,然后释放next节点,让node链接其下一个节点
        ListNode* next = node->next;
        node->val = next->val;
        node->next = next->next;
        delete next;
    }
};

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

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

思路:快慢指针,因为要删除倒数第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* removeNthFromEnd(ListNode* head, int n) {
        if(head==nullptr || n<0)
        {
            return head;
        }
        //快慢指针,二者从头开始
        ListNode* pre = nullptr;
        ListNode* fast = head;
        ListNode* slow = head;
        //快指针先走n步
        //while(n--) ->走n步  while(--n)->走n-1步
        while(n--)
        {
            if(!fast) return nullptr;//如果提前走到空,说明没有倒数第n个节点 -> n>链表长度
            fast = fast->next;
        }
        //fast和slow一起走,注意前驱指针也要一起走！删除之后要进行链接
        while(fast)
        {
            fast = fast->next;
            pre = slow;//前驱指针跟在slow后面
            slow = slow->next;
        }
        //判断删除的是否是头节点
        if(slow == head)
        {
            head = head->next;//换头
        }
        else
        {
            pre->next = slow->next;//pre slow slow->next  slow就是要删除的节点
        }
        delete slow;
        return head;
    }
};

92. 反转链表 II

https://leetcode.cn/problems/reverse-linked-list-ii/

头插法

我们最好使用哨兵位节点！防止头节点就是要反转的第一个节点！

由实例中可以得知:这里的节点编号从1开始,即头节点是第一个节点

反转的时候需要知道前一个节点的位置,所以需要双指针同时移动,pre跟在cur的后面, 然后pre cur cur->next三者进行重新链接 类似于头插

如图:类似于牛客的题目

cur：指向待反转区域的第一个节点left
next(temp)：永远指向 cur 的下一个节点，循环过程中，cur 变化以后 next 会变化
pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变

/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
        //链表为空直接返回,不需要反转
        if(head == nullptr)
        {
            return head;
        }
        //因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        ListNode* pHead = new ListNode(-1);//哨兵位节点
        pHead->next = head;//哨兵位连接原链表
        ListNode* pre = pHead;
        ListNode* cur = head;
        //头节点是第一个节点,所以从1开始,而不是从0开始
        //先来到第left个节点的位置
        for(int i = 1;i<left;i++)
        {
            pre = cur;
            cur = cur->next;
        }
        //此时cur就是第left个节点, pre就是其前一个节点
        for(int i = left;i<right;i++)
        {
            ListNode* temp = cur->next;
            //pre cur next(temp)进行链接反转
            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        return pHead->next;
    }
};