英文:
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->next) return;
ListNode *p = head;
vector<ListNode*> nodes;
while(p){
nodes.push_back(p);
p = p->next;
}
delete p;
for(int front=0; front<(nodes.size()-2); front++){
int back = nodes.size() - 1;
nodes[back]->next = nodes[front]->next;
nodes[front]->next = nodes[back];
nodes.pop_back();
back = nodes.size() - 1;
nodes[back]->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 <= Node.val <= 1000
I tried debugging the code and found out the condition
front<(nodes.size()-2)
gives true when the input size is 1.
I think it should be false as 0<(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 < 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< std::ssize(nodes)-2; front++){
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论