力扣代码题报释放后访问

Question

在刷力扣第三题“无重复字符的最长字符串”时遇到问题。
题目：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
比如输入abcabcbb，返回3，因为最长子串是abc。
以下是我的代码，通过建立单向链表和查询的方式，在linux系统上运行没问题，使用AdressSanitizar编译运行还是没问题，但力扣运行就报heap-use-after-free。网络上说可能是链表尾节点没有指空，但我的链表节点都经过了初始化，还有说因为访问了悬挂指针，经检查也没发现有悬挂指针，实在看不出来问题在哪了。
解释一下，最后的int lengthOfLongestSubstring(char* s)是主要函数，使用时就是:
s="abcdef";printf("%d\n",lengthOfLongestSubstring(s));

typedef struct LinkNode{
    char str;
    struct LinkNode* next;
}linknode;

struct LinkNode* create_node(char val)  //给出数值，创建链表，返回指针
{
    struct LinkNode *tmp2 = (linknode *)malloc(sizeof(linknode));
    tmp2->str = val;
    tmp2->next = NULL;
    return tmp2;
}

int makesure(linknode *pnode, char val)  //查询链表里有没有val，有返回-1，没有返回0
{
    linknode *p = pnode;
    while(p->str != val)
    {
        if(NULL == p->next )
        {
            return 1;
        }
        p = p->next;
    }
    return -1;
}

void add_node(linknode *pnode, char val0)  //尾插
{
    linknode *tmp = pnode;
    if(0 == pnode->str)
    {
        pnode->str = val0;
        return;
    }
    while(tmp->next != NULL)
    {
        tmp = tmp->next;
    }
    tmp->next = create_node(val0);
}

void clean_node(linknode *linkhead)   //清空链表，但保留头
{
    linkhead->str = 0;
    if(linkhead->next == NULL){
        return;
    }
    else if(linkhead->next->next == NULL){
        free(linkhead->next);
        return;
    }
    
    linknode * tmp0 = linkhead->next;
    linknode * tmp1 = linkhead->next->next;
    linkhead->next = NULL;
    while(1)
    {
        free(tmp0);
        tmp0 = tmp1;
        if(NULL == tmp1->next){
            
            free(tmp1);
            break;
        }
        tmp1 = tmp1->next;
    }
}

int lengthOfLongestSubstring(char* s) {
    int ret = 0;
    int ret0 = 0;
    linknode *head = create_node(0);

    for(int i = 0; i < strlen(s); i++)
    {   
        
        if(makesure(head, s[i]) == 1)
        {
            add_node(head, s[i]);
            ret++;  
        }
        else
        {   
            clean_node(head);
            if(ret > ret0)
            {
                ret0 = ret;
                
            }
            ret = 1;
            head->str = s[i];
        }
        if(i == strlen(s) - 1)
        {
            clean_node(head);
            if(ret > ret0)
            {
                ret0 = ret;
            }
        }
    }
    free(head);
    return ret0;
}

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

解答

力扣第三题“无重复字符的最长字符串”是一个常见的滑动窗口问题。下面是我的解答：

你的代码可以使用哈希表来实现，但是你可以使用双指针来实现，时间复杂度更低。下面是一个使用双指针的解决方案：

int lengthOfLongestSubstring(char * s){
    int n = strlen(s);
    int start = 0, end = 0;
    int maxLen = 0;
    int charSet[128] = {0};

    while (end < n) {
        if (charSet[s[end]] > 0) {
            start = max(start, charSet[s[end]]);
        }
        charSet[s[end]] = end + 1;
        end++;
        maxLen = max(maxLen, end - start);
    }
    return maxLen;
}

这个解决方案使用两个指针 start 和 end 来表示当前的子串。charSet 是一个哈希表，用于记录每个字符的最后出现的位置。然后，我们遍历字符串，遇到重复字符时，更新 start 指针，使得当前子串不包含重复字符。最后，我们返回当前子串的长度。

这个解决方案的时间复杂度是 O(n)，空间复杂度是 O(1)。