Why do I use "headA++", it's "time limit exceeded", but headA=headA->next, it's AC?


  • 0
    L
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            int lenA = 0;
            int lenB = 0;
            ListNode *_headA, *_headB;
            _headA = headA; _headB = headB;
            while(_headA){
                //_headA++
                _headA = _headA->next;
                lenA++;
            }
            while(_headB){
                //_headB++
                _headB = _headB->next;
                lenB++;
            }
            while(lenA>lenB){
                //headA++
                headA = headA->next;
                lenA--;
            }
            while(lenA<lenB){
                //headB++
                headB = headB->next;
                lenB--;
            }
            while(headB != headA){
                //headA++;headB++;
                headA = headA->next;
                headB = headB->next;
            }
            return headA;
        }
    };
    
    1. get the length of A and B;
    2. if length of A is bigger than length of B, then A is backward.
    3. B is same as A
    4. if length of A equals length of B, then compare

    but if I use headA++ to replace headA->next, it will get TLE


  • 1
    K

    Its because head++ is not same as head->next. This can be explained from pointer arithmetic. To understand pointer arithmetic, let us consider that ptr is an integer pointer which points to the address 1000. Assuming 32-bit integers, let us perform the following arithmetic operation on the pointer:ptr++
    Now, after the above operation, the ptr will point to the location 1004 because each time ptr is incremented, it will point to the next integer location which is 4 bytes next to the current location. This operation will move the pointer to next memory location without impacting actual value at the memory location. If ptr points to a character whose address is 1000, then above operation will point to the location 1001 because next character will be available at 1001.

    Similarly let say head was pointing to address 1000, so after the operation head++, head will point to 1000+sizeof(ListNode). Which may or may not be address of the head->next. Because in linked list data structure each node may or may not be stored in contiguous memory.

    For more information, see the difference between memory structure of array and linked list here.
    Difference Between Array and Linked List


  • 0
    L

    Thank you for your answer.
    So as you say, is it always not safe to use "pointer++", even this pointer is a integer pointer?


  • 0
    K

    Yes, It is not always to safe pointer++. Pointer++ might not even pointing to a valid memory.


  • 0
    L

    Thank you again~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.