尝试反转链表时显示分段错误

Question

我尝试使用此代码反转单向链表的一部分。

这里的startOfSec是要反转的链表段起始节点的指针，endofSec是指向该段最后一个节点的指针。

现在，使用这段代码，我遇到了分段错误，但是如果我将 endOfSec->next 替换为 NULL（我正在更改指针的值，指向该部分的最后一个节点（即被反转）原始链表，也为NULL）在while循环条件下，它完美运行！

void reverseList(ListNode* startOfSec, ListNode *endOfSec){

    ListNode *prev = NULL;
    ListNode *curr = startOfSec;
    ListNode *nxt;
    while(curr!=endOfSec->next){
        nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
}

Callsite:
//code to get start and end pointers
reverseList(start, end);

我希望我的代码能够反转列表的部分，而不需要将 end->next 指针设置为 NULL。

Answer 1

此代码存在一些问题，其中一些问题比其他问题更容易解决。对于这个特定的分段错误，代码演练揭示了原因。让我们看一个简单的例子会发生什么。（您应该自己学习如何手动或使用调试器来执行此操作。）

start -> end -> NULL

这是一个包含两个元素的列表，一个名为 "start"，另一个名为 "end"。嗯，假设 "start" 和 "end" 也是指向节点的指针。有点模棱两可，不过这次应该不会出问题了。现在反转列表。

reverseList(start, end);

在 reverseList 循环的第一次迭代之前（即初始化之后），您的数据如下所示。

startOfSec == start
endOfSec == end;     endOfSec->next == NULL;
prev == NULL
curr == start
nxt == /* uninitialized */

start -> end -> NULL

第一次迭代后，数据已经更新。

startOfSec == start
endOfSec == end;     endOfSec->next == NULL;
prev == start
curr == end
nxt == end

start -> NULL
end -> NULL

第二次迭代后，数据已经更新。

startOfSec == start
endOfSec == end;     endOfSec->next == start;
prev == end
curr == NULL
nxt == NULL

end -> start -> NULL

恭喜，名单已反转。现在我们要做的就是退出循环，所以我们希望 curr 等于 endOfSec->next。但是，NULL 不等于 start，因此我们继续进行第三次迭代，并在尝试读取 curr->next (a.k.a.NULL->next) 时崩溃.

总的来说，您需要修改跟踪部分开头和结尾的方式以进行反转。当前崩溃的发生是因为您忘记了该部分的结尾。（也许改为检查 prev != endOfSec ？）如果该部分的末尾不是列表的末尾，您也会遇到问题（反转部分之后的列表部分将丢失），但这是通过更改 prev 的初始化方式很容易修复。我看到的最大问题是当该部分的 beginning 不是列表的开头时——更改 singly-linked 列表需要修改更改前的节点（a.k.a.startOfSec).

之前的节点

尝试反转链表时显示分段错误

Showing Segmentation Fault when Attempting to Reverse a Linked List

c++

reverse

singly-linked-list