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?

Answer 1

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.