反转链表

大链表吱呀吱悠悠地转♪

这里~的风景呀真奇怪♪

天在转♪ 地在转♪

还有一个刷题的小笨蛋♪

反转链表！经久不衰的送分题！

反转整个链表

206.反转链表

给你单链表的头节点head，请你反转链表，并返回反转后的链表。

提示：

• 链表中节点的数目范围是[0, 5000]
• -5000 <= Node.val <= 5000

迭代和递龟递归都可以哦！

迭代解法

遍历整个链表，反转一下next指针的方向就好了，非常简单，不赘述啦！

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

递归解法

递归的版本就比较复杂一些，关键在于反向工作。假设链表的其余部分已经被反转，那么考虑如何反转之前的部分。

假设链表长这样：
$$
n_1 \rightarrow \dots n_{k - 1} \rightarrow n_k \rightarrow n_{k + 1} \rightarrow \dots \rightarrow n_m \rightarrow nullptr
$$

如果我们已经将$n_{k + 1} \rightarrow \dots \rightarrow n_m$的部分反转，目前来到了$n_k$。那么我们希望$n_k$的下一个结点$n_{k + 1}$能指向$n_k$。即：
$$
n_k\rightarrow next\rightarrow next = n_k
$$

那就开始递归吧！从后往前反转链表，就一直一直往后冲。但是需要一个出口呀，这里设置当结点为空或到达链表末端时返回该结点，相当于是新链表的头部啦！之后就是之前分析的部分啦，执行head->next->next = head;更改指针的方向。但是要记得把当前指针的next设为空哦，不然就会有环啦！

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

反转部分链表

反转所有链表还是太简单了（单指迭代，上点有意思的：反转部分链表！

92.反转部分链表 II

截取需要反转部分单独操作

最容易想到的思路就是，借鉴之前反转整个链表的想法，弄四个指针，两个指针在开始反转部分的前一个和开始部分，设为pre和leftNode；两个指针在反转部分的结束部分和后一个结点，设为rightNode和curr。将pre和rightNode的next设为空，将需要反转的部分独立出来，单独进行反转。反转完成后再接回原来的链表。

class Solution {
private:
    void reverseLinkedList(ListNode *head) {
        // 也可以使用递归反转一个链表
        ListNode *pre = nullptr;
        ListNode *cur = head;

        while (cur != nullptr) {
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
    }

public:
    ListNode *reverseBetween(ListNode *head, int left, int right) {
        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;

        ListNode *pre = dummyNode;
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }

        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode *rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode->next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode *leftNode = pre->next;
        ListNode *curr = rightNode->next;

        // 注意：切断链接
        pre->next = nullptr;
        rightNode->next = nullptr;

        // 第 4 步：同第 206 题，反转链表的子区间
        reverseLinkedList(leftNode);

        // 第 5 步：接回到原来的链表中
        pre->next = rightNode;
        leftNode->next = curr;
        return dummyNode->next;
    }
};

一次遍历

上一个方法当需要反转的区间长度非常大的时候，时间开销会变大，极端情况下需要遍历两次链表。考虑使用“头插法”实现一次遍历的反转部分链表。

整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。

下面我们具体解释如何实现。使用三个指针变量 pre、curr、next来记录反转的过程中需要的变量，它们的意义如下：

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

（要画的图太多了，直接手写了

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        ListNode *next;
        for (int i = 0; i < right - left; i++) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return dummyNode->next;
    }
};