leetcode92 反转链表

puningyyb / 2024-09-27 / 原文

 * 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) {
        ListNode dummy(0,head);  //新建一个头节点，空的
        ListNode* p0 = &dummy;
        for(int i = 0; i < left -1 ; i++){
            p0 = p0->next;   //找到左边第一个的前一个节点指针
        }
        //p0表示左边第一个的前一个节点指针

        ListNode* pre = nullptr;   //pre表示当前节点的前一个位置
        ListNode* cur = p0->next; //cur表示当前的位置
        for(int i = 0 ; i < right - left + 1; i++){
            ListNode* nxt = cur->next;
            cur->next = pre;   //l-r之间的节点指针方向改变，即当前节点的next指针指向上一个
            pre = cur;     //pre变成当前节点的位置
            cur = nxt;   //当前的节点变成下一个节点位置
        }
        p0->next->next = cur;   //细品  ，左边第一个节点指向r的下一个节点的位置

        p0->next = pre;   //p0的前一个节点与r节点连接
        return dummy.next;
    }
};```