反转链表.md

反转链表

1.92. 反转链表 II

一次遍历，时间复杂度O(n), 空间复杂度O(1)

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        ListNode *dummy = new ListNode(0);
        dummy -> next = head;
        ListNode *pre = dummy;
    
        for(int i = 0 ; i < left - 1 ; i ++)
            pre = pre -> next;
        
        ListNode *next;
        ListNode *cur = pre -> next;
        for(int i = left ; i < right ; i ++)
        {
            next = cur -> next;
            cur -> next = next -> next;
            next -> next = pre -> next;
            pre -> next = next;
        }

        return dummy -> next;
    }
};

思想：每遍历到一个结点，便将这个结点放到需要反转部分的头部

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