【6.6】206. 反转链表 3. 无重复字符的最长子串

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

ex1:
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

ex2:
输入：head = [1,2]
输出：[2,1]

ex3:
输入：head = []
输出：[]

1. 迭代法：迭代的方法就是从前往后对链表进行处理，在翻转的过程中要维持一个n指针，一个n+1指针，在处理的过程中首先保存n+2，然后将n+1的next指向n，然后迭代返回n+1和n+2。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
		ListNode* prev = nullptr;
        ListNode* curr = head;
        
        while(curr) {
            ListNode* next = curr->next; // 这里就是保存n+2的过程
            curr->next = prev; // 这里将n+1指向n
            prev = curr; // 迭代返回prev=n+1，之前是prev=n
            curr = next; // 迭代返回curr=n+2，之前是curr=n+1
        }
        return prev;
    }
};

2. 递归法：使用递归法返回newhead，然后每次仅对当前节点进行处理，返回的同样是newhead。并且在处理的过程中需要将head next指向nullptr避免造成环。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
};

• 如果不加head->next = nullptr;这句代码会让链表中出现环，并且会输出一个链表入口处有环的链表
• 如果输入为有环链表，对于迭代法可以输出翻转后的循环链表，对于递归法会死循环

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

输入: s = "abcabcbb"
输出: 3

1. 双指针法，没重复就在查找表中+1，右指针向右移动一位，重复就在查找表中对左指针的符号-1，然后左指针向右移动一位

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int symbol[1000] = {0};
        if(s.size() == 0 || s.size() == 1) return s.size(); 
        int left = 0;
        int ret = 0;
        for(int i = 0; i < s.size(); i++) {
            if(symbol[s[i]] == 0) {
                ret = max(ret, i - left + 1);
                symbol[s[i]] += 1;
            } else {
                symbol[s[left]] -= 1;
                left += 1;
                i -= 1;
            }
        }
        return ret;
    }
};

2. 使用unordered_set的find，erase，insert的方法便捷实现重复的情况

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        unordered_set lookup;
        int ret = -1;
        int ptr = 0;
        for(int i=0; i
            while (lookup.find(s[i]) != lookup.end()){
                lookup.erase(s[ptr]);
                ptr++;
            }
            ret = max(ret,i-ptr+1);
            lookup.insert(s[i]);
        }
        return ret;
    }
};