for loop is executing even though the condition should be false

Question

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?

Well if you have a concrete test-case that you can use to replicate the problem reliably, why don't you write it into a hard-coded [mre], and [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your program? — Some programmer dude, Jun 12 '23 at 08:08
As a hint about your problem: `nodes.size()` returns an *unsigned* value. Wrapping around zero (like subtracting `1` or `2` from `0`) will lead the result to become *very big*. Something a decent course, tutorial or [book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) should have taught you. Please don't use sites like "leetcode" to learn the basics of programming or a language, that's just not their purpose. Using such sites doesn't make you a "leet" programmer, all they seem to do is teach bad habits, bad code, and sometimes even *invalid* code. — Some programmer dude, Jun 12 '23 at 08:10
tip for debugging: Do not put too much into a single line. Try `auto x = nodes.size()-2; if (front < x)` You will clearly see why `0 < (1u-2)` is `true` — 463035818_is_not_an_ai, Jun 12 '23 at 08:11
Turn up your compiler warnings, and do NOT ignore them (signed/unsigned mismatches). Also `front<(nodes.size()-2)` is fragile... what happens if there are 0 or 1 nodes in your list?. Change your `int front` to `std::size_t front`. Rule : your code should compile without warnings, they mean something. — Pepijn Kramer, Jun 12 '23 at 08:13
C++ does not work the same as mathematics, especially where unsigned types or floating point types are concerned. — john, Jun 12 '23 at 08:29
@john sorry for the nitpick, but unsigned arithmetics is covered by mathematics, even flaoting point arithmetics is, its just not the naive intuitive arithmetics one is used to in daily life — 463035818_is_not_an_ai, Jun 12 '23 at 08:39
See also [Why does (0 > v.size()-1) evaluate to false for an empty vector?](https://stackoverflow.com/q/18813963) — JaMiT, Jun 12 '23 at 09:13

trincot · Accepted Answer · 2023-06-12T09:05:45.557

3

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.

edited Jun 12 '23 at 09:05

answered Jun 12 '23 at 08:11

trincot

317,000
35
244
286

score 1 · Answer 2 · answered Jun 12 '23 at 08:21

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++){

for loop is executing even though the condition should be false

2 Answers2