Li Kou brush questions (2022-6-28)

Reverse a linked list

Here's the head node of the list  head , Please reverse the list , And return the inverted linked list .

Example 1：

Input ：head = [1,2,3,4,5]
Output ：[5,4,3,2,1]
Example 2：

Input ：head = [1,2]
Output ：[2,1]
Example 3：

Input ：head = []
Output ：[]

If you simply put the first 1 A node points to NULL, Will be the first 2 The first node points to the 1 The address of the node , Then we will lose the first 3 The address of the node , Therefore, it is impossible to 3 The first node points to the 2 Nodes . So we need three pointers .

ListNode* reverseList(ListNode* head) {

        ListNode *p =nullptr;
        ListNode *tmp;
        while(head){
            tmp = head->next;
            head->next = p;
            p = head;
            head = tmp;
        }
        return p;

}

The longest string without duplicate characters

Given a string s , Please find out that there are no duplicate characters in it   Longest substrings   The length of .

Example  1:

Input : s = "abcabcbb"
Output : 3 
explain : Because the longest substring without repeating characters is "abc", So its length is 3.
Example 2:

Input : s = "bbbbb"
Output : 1
explain : Because the longest substring without repeating characters is "b", So its length is 1.
Example 3:

Input : s = "pwwkew"
Output : 3
explain : Because the longest substring without repeating characters is  "wke", So its length is 3.
     Please note that , Your answer must be Substring The length of ,"pwke"  Is a subsequence , Not substring .

Specify left and right positions , Move the left pointer one space to the right , Indicates to start enumerating the next character as the starting position , And then we can keep moving the right pointer to the right , But we need to ensure that there are no duplicate characters in the substring corresponding to these two pointers . At the end of the move , This substring corresponds to the longest substring that does not contain repeated characters starting with the left pointer .

public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if(len == 0) return 0;
        int start = 0 , end = 0;
        int ret = 0;// Substring length 
        while(end < len){ 
            for(int j = start ; j < end ; j++){
                if(s.charAt(j) == s.charAt(end)){// At present end The subscript character and subscript are j When the characters are the same 
                    ret = Math.max(ret , end - start);// Find the maximum substring length 
                    start = j + 1;// slide start Just go to the end of the repeating character 
                }
            }
            end++;// There are no duplicate characters , that end Move backward , Lengthen the window length to continue a new round of traversal comparison 
        }
        return Math.max(ret , end - start);// Make a final comparison 
    }