Leetcode92. 反转链表 II

Every day a Leetcode

题目来源：92. 反转链表 II

解法1：模拟

注意 STL 的 reverse() 是左闭右开的。

代码：

class Solution
{
public:ListNode *reverseBetween(ListNode *head, int left, int right){vector<int> nums = getNums(head);reverse(nums.begin() + left - 1, nums.begin() + right);return buildList(nums);}// 辅函数 - 遍历链表vector<int> getNums(ListNode *head){ListNode *p = head;vector<int> nums;while (p){nums.push_back(p->val);p = p->next;}return nums;}// 辅函数 - 根据数组建立链表ListNode *buildList(vector<int> &nums){ListNode *dummy = new ListNode(0);ListNode *cur = dummy;for (int &num : nums){ListNode *node = new ListNode(num);cur->next = node;cur = cur->next;}return dummy->next;}
};

结果：

复杂度分析：

时间复杂度：O(N)，其中 N 是链表总节点数。最坏情况下，需要遍历整个链表。

空间复杂度：O(N)，其中 N 是链表总节点数。用到了辅助数组 nums 存储链表元素。

解法2：穿针引线

反转 left 到 right 部分以后，再拼接起来。

我们还需要记录 left 的前一个节点，和 right 的后一个节点。如图所示：

代码：

class Solution
{
public:ListNode *reverseBetween(ListNode *head, int left, int right){ListNode *dummy = new ListNode(0, head);ListNode *pre = dummy;// 从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点for (int i = 0; i < left - 1; i++)pre = pre->next;// 从 pre 再走 right - left + 1 步，来到 right 节点ListNode *rightNode = pre;for (int i = 0; i < right - left + 1; i++)rightNode = rightNode->next;// 切断出一个子链表（截取链表）ListNode *leftNode = pre->next;ListNode *cur = rightNode->next;// 切断链接pre->next = nullptr;rightNode->next = nullptr;// 反转链表的子区间reverseLinkedList(leftNode);// 接回到原来的链表中pre->next = rightNode;leftNode->next = cur;return dummy->next;}// 辅函数 - 反转链表void reverseLinkedList(ListNode *head){ListNode *pre = nullptr;ListNode *cur = head;while (cur){ListNode *next = cur->next;cur->next = pre;pre = cur;cur = next;}}
};

结果：

复杂度分析：

时间复杂度：O(N)，其中 N 是链表总节点数。最坏情况下，需要遍历整个链表。

空间复杂度：O(1)，只用到了常数个指针变量。

解法3：一次遍历「穿针引线」反转链表（头插法）

整体思想是：

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

下面的图展示了整个流程：

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

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

我们使用 ①、②、③ 标注「穿针引线」的步骤。

操作步骤：

1. 先将 curr 的下一个节点记录为 next；
2. 执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
3. 执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；
4. 执行操作 ③：把 pre 的下一个节点指向 next。

第 1 步完成以后「拉直」的效果如下：

第 2 步，同理。同样需要注意 「穿针引线」操作的先后顺序。

第 2 步完成以后「拉直」的效果如下：

第 3 步，同理。

第 3 步完成以后「拉直」的效果如下：

结果：

复杂度分析：

时间复杂度：O(N)，其中 N 是链表总节点数。最坏情况下，需要遍历整个链表。

空间复杂度：O(1)，只用到了常数个指针变量。