c++ 删除链表中间节点时出现运行时错误

9o685dep 于 2022-12-05 发布在其他

关注(0)|答案(2)|浏览(240)

我正在处理LeetCode问题2095. Delete the Middle Node of a Linked List：
给出了一个链表的head。删除中间节点**，* 返回修改后链表的头 *。
大小为n的链接列表的中间节点是使用基于0的索引从开始算起的第⌊n / 2⌋个节点，其中⌊x⌋表示小于或等于x的最大整数。

对于n = 1、2、3、4和5，中间节点分别是0、1、1、2和2。

这是我的密码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        
        ListNode *slow = head ;
        ListNode *fast = head ;
        
        
        if(head==NULL){
            return head ;
        } 
        if(head->next == NULL){
            delete head ;
            return head ;
        }
        
        while(fast->next && fast){
            slow = slow->next ;
            fast = fast->next->next ;
        } 
        
        ListNode *temp = head ;
        
        while(temp->next != slow){
            temp=temp->next ;
        } 
        
        
        temp->next = slow->next ;
        delete slow ;
        
        return head ;
        
        
    }
};

我收到如下运行时错误：

Line 27: Char 21: runtime error: member access within null pointer of type 'ListNode' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:36:21

我做错了什么？

c++

来源：https://stackoverflow.com/questions/73483197/runtime-error-when-deleting-the-middle-node-of-a-linked-list

2条答案

按热度按时间

g52tjvyc1#

有两个问题：

在delete head之后，您不应该执行return head，因为这样会返回一个对已释放内存的引用，测试平台肯定会访问它来测试结果，从而导致未定义的行为（或者您得到的这个错误）。
while条件应该 * 首先 * 检查fast不是nullptr，* 然后 * 检查fast->next是什么，所以这些条件应该以相反的顺序出现。

有了这些修复程序，它将工作。
不过，很遗憾，您的代码还需要另一个指针，（temp）遍历列表以找到slow之前的节点。最好确保slow指向前面的节点...这样就不需要遍历列表了。您可以通过在开始（第一个）循环之前为fast提供两个步骤的优势来实现这一点。
下面的代码修复了两个问题，并进行了我上面提到的改进：

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }
        
        if (head->next == nullptr) {
            delete head;
            return nullptr; // Don't return a reference to freed memory!
        }

        ListNode *slow = head;
        // Already advance `fast` with 2 steps, 
        //   so `slow` ends up BEFORE the node to delete
        ListNode *fast = head->next->next; 
        
        // First check that the fast pointer is not nullptr before accessing `->next`
        while (fast && fast->next) { 
            slow = slow->next;
            fast = fast->next->next;
        } 
        
        // No need for `temp` when we make sure `slow` is at the preceding spot
        // Reuse `fast` for referencing the node to delete
        fast = slow->next;
        slow->next = fast->next;
        delete fast;
        
        return head;
    }
};

赞(0）回复(0）举报 2022-12-05

xyhw6mcr2#

我们可以通过遍历所有元素来解决这个问题。
时间复杂度为O（N+N/2）。
然后我们可以使用另一种方法，称为乌龟方法。
在该方法中，我们在每次迭代中将慢速指针移动一，并将快速指针移动二。
与此方法相关的解决方案是：https://learningwithsapnil.blogspot.com/2022/12/leetcode-middle-of-linked-list-solution.html

赞(0）回复(0）举报 2022-12-05

我来回答

c++ 删除链表中间节点时出现运行时错误

2条答案

相关问题

热门标签

最新问答