I am solving LeetCode question:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 10⁵].
• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

Using C I get the error below:

=================================================================
==42==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000098 at pc 0x00000037ac7d bp 0x7ffc1760fda0 sp 0x7ffc1760fd98
READ of size 8 at 0x602000000098 thread T0
    #2 0x7f5a8c3e70b2  (/lib/x86_64-linux-gnu/libc.so.6 0x270b2)
0x602000000098 is located 8 bytes inside of 16-byte region [0x602000000090,0x6020000000a0)
freed by thread T0 here:
    #3 0x7f5a8c3e70b2  (/lib/x86_64-linux-gnu/libc.so.6 0x270b2)
previously allocated by thread T0 here:......

Here is my code:

/*code only in VS 
#include <iostream>
using namespace std;
  struct ListNode {
     int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };*/
 
class Solution {
public:

    bool isPalindrome(ListNode* head) {
        if (!head->next) {
            return true;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* prev = slow;
        ListNode* current = prev->next;
        while (current) {
            ListNode* temp = current->next;
            current->next = prev;
            prev = current;
            current = temp;
        }
        while (head != slow)
        {
            if (head->val != prev->val) {
                return false;
            }
            head = head->next;
            prev = prev->next;
        }
        return true;
    }
};
/*code only in VS 
int main()
{
    ListNode* a = new ListNode(1);
    ListNode* b = new ListNode(0);
    ListNode* c = new ListNode(3);
    ListNode* d = new ListNode(4);   //[1,0,3,4,0,1]
    ListNode* e = new ListNode(0);
    ListNode* f = new ListNode(1);
    a->next = b;
    b->next = c;
    c->next = d;
    d->next = e;
    e->next = f;
    Solution solution;
    cout << solution.isPalindrome(a);

}*/

I can run it and get the right answer in my IDE (Visual Studio 2019 Community), but get an error in the LeetCode submission.

Any idea why this would happen?

CodePudding user response：

The error occurs when the Leet Code test system will try to release the memory used by the previous test case, before launching the next one.

Your code leaves the list in a state where it will run in cycles: the node that follows slow has been rewired by your code to point back to slow.

We can imagine how the Leet Code clean-up code will free the node that slow refers to, then free the next node's memory, and then arrive again at slow which was already freed/deleted. This is the cause of this error. It is therefore important that you leave the list in a consistent state, where it has the original number of nodes, and there are no cycles.

To resolve the error quicly, just add this line before the last loop:

slow->next = nullptr;

However, this leaves the second (reversed) half of your list unreachable for Leet Code to clean up. That's not really fair (although fast). To do it properly, make slow stop at the left side of the center when the list size is even (by moving fast one step ahead), and then rewire the tail of the first half with the (new) head of the second half (which was reversed):

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head->next) {
            return true;
        }
        ListNode* slow = head;
        ListNode* fast = head->next; // Stop loop sooner when size is even
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* prev = nullptr; // this will be assigned to the new tail
        ListNode* current = slow->next;
        while (current) {
            ListNode* temp = current->next;
            current->next = prev;
            prev = current;
            current = temp;
        }
        slow->next = prev; // link tail of first half to head of reversed part
        while (prev) // Continue the walk in second half until the list's end
        {
            if (head->val != prev->val) {
                return false;
            }
            head = head->next;
            prev = prev->next;
        }
        return true;
    }
};