for循环正在执行,尽管条件应该为假。

huangapple go评论82阅读模式
英文:

for loop is executing even though the condition should be false

问题

在解决这个leetcode问题时,我的代码通过了所有的测试,但当链表的大小为1时,会出现运行时错误。如果我取消注释这里的代码,它可以正常工作,尽管我认为它应该能够在不单独处理边缘情况的情况下工作。

问题如下:
给定一个单链表的头部。链表可以表示为:

L0 → L1 → … → Ln - 1 → Ln

重新排列列表以满足以下形式:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

您不能修改列表节点中的值。只能更改节点本身。
约束条件:

列表中的节点数在[1, 5 * 10^4]范围内。
1 <= Node.val <= 1000

我尝试调试代码并发现条件

front<(nodes.size()-2)

在输入大小为1时返回true。

我认为它应该返回false,因为0 < (1-2) 显然不成立。
有人可以解释一下为什么会出现这种情况吗?

英文:

So, I was solving this leetcode problem and my code passes all the tests but gives a runtime error when the size of the linked list is 1. If I uncomment the code here it works, though I think it should work without handling the edge case separately.

class Solution {
public:
    void reorderList(ListNode* head) {
        // if(!head || !head-&gt;next) return;
        ListNode *p = head;
        vector&lt;ListNode*&gt; nodes;
        while(p){
            nodes.push_back(p);
            p = p-&gt;next;
        }
        delete p;
        for(int front=0; front&lt;(nodes.size()-2); front++){
            int back = nodes.size() - 1;
            nodes[back]-&gt;next = nodes[front]-&gt;next;
            nodes[front]-&gt;next = nodes[back];
            nodes.pop_back();
            back = nodes.size() - 1;
            nodes[back]-&gt;next = NULL;
        }
    }
};

The problem is as follows:
You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Constraints:

The number of nodes in the list is in the range [1, 5 * 104].
1 &lt;= Node.val &lt;= 1000

I tried debugging the code and found out the condition

front&lt;(nodes.size()-2)

gives true when the input size is 1.

I think it should be false as 0&lt;(1-2) is clearly not true.
Can someone explain to me why this is happening?

答案1

得分: 3

nodes.size() 是类型为 size_type 的,它是一个无符号类型。因此 (nodes.size()-2) 也是相同类型的,永远不会是负数...它会变成一个很大的无符号整数。

所以将条件改为 front + 2 < nodes.size()

现在下一个挑战是提出一个不需要 O(n) 辅助空间(你的向量)的解决方案。提示:

!将列表分成两半,反转第二半,然后合并。

英文:

nodes.size() is of type size_type which is an unsigned type. By consequence (nodes.size()-2) will be of the same type and never negative... it will wrap around to a large unsigned integer.

So change the condition to front + 2 &lt; nodes.size()

Now the next challenge is to come up with a solution that does not require O(n) auxiliary space (your vector). Hint:

>! Split list in half, reverse second half, and zip.

答案2

得分: 1

vector::size 返回一个无符号整数。无符号整数会环绕。0u - 1 是最大的无符号值。您应该注意警告。比较有符号和无符号值应该会产生警告。

自从 C++20 以后,您可以使用 std::ssize 来获取容器的大小作为有符号值:

for(int front=0; front < std::ssize(nodes)-2; front++){
英文:

vector::size returns an unsigned integer. Unsigned integers wrap around. 0u - 1 is the largest unsigned value. You should pay attention to warnings. There should be a warning for comparing a signed with an unsigned value.

Since C++20 you can use std::ssize to retrieve the size of a container as a signed value :

for(int front=0; front&lt; std::ssize(nodes)-2; front++){

huangapple
  • 本文由 发表于 2023年6月12日 15:57:27
  • 转载请务必保留本文链接:https://go.coder-hub.com/76454599.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定