>我正在研究一个反向链表问题，您可以在链接列表结构中反转子列表。子列表由left和right定义，这是您必须反转的部分。当使用较小尺寸的链表(大小为 2)时，它工作正常，但当处理 5 个左右的元素时，它开始失败。这是因为(如示例中所示)我不太了解如何维护原始头部并连接到我现在反转的子列表。我已经尝试过head->next = prev;但这不起作用并导致nullptr内存访问错误。
对这种数据结构很陌生，希望能深入了解我如何解决这个问题。
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(0, head);
ListNode* prev = nullptr;
ListNode* current = head;
int counter = 1;
while (current != nullptr)
{
if (counter == left)
{
ListNode* lastKnownParent = current;
ListNode* n = nullptr;
while (counter <= right)
{
n = current->next;
current->next = prev;
prev = current;
current = n;
counter++;
}
lastKnownParent->next = current;
}
else {
counter++;
current = current->next;
}
}
dummy->next->next = current;
dummy->next = prev;
return dummy->next;
}
使用较小尺寸的成功：input: [3,5] left = 1, right = 2: Output: [5,3]
较大尺寸时失败：input: [1,2,3,4,5] left = 2, right = 4: Output: [2,4,3,2,5]
有几个问题：
-
函数底部的线条不好。他们硬编码说需要在列表的前两个节点发生一些更改，但是当例如必须在节点 4 和 6 之间进行反转时，这是没有意义的。所以这两行应该删除：
dummy->next->next = current; dummy->next = prev; -
lastKnownParent前面的节点必须更新其next指针，但问题是不再直接引用该节点。我上面引用的陈述可能是为了达到那个节点，但它必须相对于left位置来完成。
为了说明出了什么问题，当我们有一个包含 8 个节点的列表并且两个给定的位置是left=4和right=6时，请查看此可视化：
当到达left并进入循环时，我们得到这个状态：
lastKnownParent
dummy head current n
↓ ↓ ↓ ↓
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 0 ├──►│ 1 ├──►│ 2 ├──►│ 3 ├──►│ 4 ├──►│ 5 ├──►│ 6 ├──►│ 7 ├──►│ 8 │
└───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘
prev == nulltptr
当到达right时，循环再进行一次迭代，然后循环退出，导致以下状态：
dummy head lastKnownParent prev current n
↓ ↓ ↓ ↓ ↓ ↓
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 0 ├──►│ 1 ├──►│ 2 ├──►│ 3 ├──►│ 4 │◄──┤ 5 │◄──┤ 6 │ │ 7 ├──►│ 8 │
└───┘ └───┘ └───┘ └───┘ └─┬─┘ └───┘ └───┘ └───┘ └───┘
▼
nullptr
然后，您的代码使用值 4 (lastKnownParent正确设置节点的next指针：
dummy head lastKnownParent prev current n
↓ ↓ ↓ ↓ ↓ ↓
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 0 ├──►│ 1 ├──►│ 2 ├──►│ 3 ├──►│ 4 │◄──┤ 5 │◄──┤ 6 │ │ 7 ├──►│ 8 │
└───┘ └───┘ └───┘ └───┘ └─┬─┘ └───┘ └───┘ └─▲─┘ └───┘
└───────────────────────┘
但是缺少一件事。仍然需要建立从节点 3 到节点 6 的链接。这似乎是您在函数结束时尝试过的事情，但您不能假设总是需要更改dummy->next->next。这取决于left，或者换句话说，这取决于lastKnownParent。问题是lastKnownParent指向需要此更新的节点的后继节点。因此，在初始化前置任务时，lastKnownParent指向前置任务。然后，您可以进行两个更新(首先更新节点 4，然后更新节点 3)。那么它看起来像这样：
dummy head lastKnownParent prev current n
↓ ↓ ↓┌──────────────────────┐↓ ↓ ↓
┌───┐ ┌───┐ ┌───┐ ┌─┴─┐ ┌───┐ ┌───┐ ┌▼──┐ ┌───┐ ┌───┐
│ 0 ├──►│ 1 ├──►│ 2 ├──►│ 3 │ │ 4 │◄──┤ 5 │◄──┤ 6 │ │ 7 ├──►│ 8 │
└───┘ └───┘ └───┘ └───┘ └─┬─┘ └───┘ └───┘ └─▲─┘ └───┘
└───────────────────────┘
为了能够更早地设置lastKnownParent一个节点，例如，即使在第一次迭代中(当尚未遇到left时)，您也可以让prev跟随current后面。
以下是更正后的代码，其中包含更改的注释：
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(0, head);
ListNode* prev = dummy; // prev follows behind current
ListNode* current = head;
int counter = 1;
while (current != nullptr)
{
if (counter == left)
{
ListNode* lastKnownParent = prev; // one node earlier
ListNode* n = nullptr;
while (counter <= right)
{
n = current->next;
current->next = prev;
prev = current;
current = n;
counter++;
}
// lastKnownParent is now one node earlier than in your code
lastKnownParent->next->next = current;
lastKnownParent->next = prev; // now the mutation is complete...
break; // ... so we don't need to iterate the remaining nodes.
}
else {
counter++;
prev = current; // prev follows behind current
current = current->next;
}
}
// Removed two statements here
return dummy->next;
}
进一步的改进
此代码假定给定的仓位有效。您可能希望对此进行改进，并确定当一个或两个超出范围或right小于left时会发生什么。
您可能还需要想出更优雅的方法来解决这一挑战。例如，您可以创建可以：
- 反转完整列表
- 将某个位置的列表拆分为两个较小的列表。
- 将较小的列表连接为一个
这可能会导致代码更具可读性。