Title: 344. Reverse character array && leetcode206 Reverse linked list

The article directories

• • • Leetcode344, reverse character array
    • • Problem description
      • Solution: Just set a temporary variable
    • Title: 541. Reverse string II
    • • Problem description
      • Train of thought
      • solution
    • Leetcode206, reverse linked list
    • • Problem description
      • Reverse linked list (head insert + change pointer)
    • 151, Reverse the words in the string (Spaces are words, so Spaces must be recognized)
    • • Solution (calling the underlying static method)
      • The four functions are expressed in their own code (in effect, they are copied from the source code)

Leetcode344, reverse character array

Problem description

Solution: Just set a temporary variable

If the key part of the problem can be solved directly by using library functions, it is recommended not to use library functions. “Consider using library functions if they are only a small part of the solution and you already know how it works internally.”

0 ^ 0 = 0; 0 ^ 1 = 1; 1 ^ 0 = 1; 1 ^ 1 = 0

class Solution {
    public void reverseString(char[] s) {
       for(int left=0,right=s.length-1; left<right; left++,right--){ char mychar = s[left]; s[left] = s[right]; s[right] = mychar; }}}Copy the code

We can change this to a while loop as follows:

class Solution { public void reverseString(char[] s) { int left =0; int right = s.length -1;while( left<right ){ char mychar = s[left]; s[left] = s[right]; s[right] = mychar; left++; right--; }}}Copy the code

There is no need for output, as soon as the program is finished executing,

Time complexity: O(N), where NN is the length of the character array. We did N over 2N over 2 swaps. Space complexity: O(1). Only constant space is used to store a number of variables.

Title: 541. Reverse string II

Problem description

Given a string s and an integer k, you need to reverse the first k characters every 2k characters from the beginning of the string

If there are less than k characters left, all the remaining characters are reversed.

If the remaining characters are less than 2K but greater than or equal to K, the first K characters are reversed and the remaining characters are left as is.

Example: Input: s = “abcdefg”, k = 2 Output: “bacdfeg”

Train of thought

solution

class Solution {
    public String reverseStr(String s, int k) {
      char[] charArray = s.toCharArray();
      for(int start=0; start<charArray.length-1; start = start + 2*k){ int i=start ; int j =Math.min(start+k-1,charArray.length -1);while(i < j){ char temp = charArray[i]; charArray[i]=charArray[j]; i++; charArray[j]=temp; j--; }}returnnew String(charArray); // Using toString() is null pointer risk, use +""Inelegantly}}Copy the code

It’s easier to write it this way, where you swap elements and move two Pointers

class Solution {
    public String reverseStr(String s, int k) {
      char[] charArray = s.toCharArray();
      for(int start=0; start<charArray.length-1; start = start + 2*k){ int i=start ; int j =Math.min(start+k-1,charArray.length -1);while(i < j){ char temp = charArray[i]; charArray[i]=charArray[j]; charArray[j]=temp; i++; j--; }}returnnew String(charArray); // Using toString() is null pointer risk, use +""Inelegantly}}Copy the code

As above, we can write a for loop as follows:

class Solution {
    public String reverseStr(String s, int k) {
      char[] charArray = s.toCharArray();
      for(int start=0; start<charArray.length-1; start = start + 2*k){for(int i=start,j =Math.min(start+k-1,charArray.length -1); i < j; i++,j--){ char temp = charArray[i]; charArray[i]=charArray[j]; charArray[j]=temp; }}returnnew String(charArray); // Using toString() is null pointer risk, use +""Inelegantly}}Copy the code

int j =Math.min(start+k-1,charArray.length -1); If the remaining elements are greater than 2K, j=start+k-1; if the remaining elements are greater than k and less than 2k, j=start+k-1; if the remaining elements are less than k, j=a. Length-1. At this point, I

About the body of the while(I <j) loop

Leetcode206, reverse linked list

Problem description

Reverse linked list (head insert + change pointer)

class Solution { public ListNode reverseList(ListNode head) { ListNode first = new ListNode(-1); // Create a new virtual head node first.next=null; ListNode cur=head; // Set next to null. This is to use code symmetry. // p execution points to the actual header of the original listwhile(cur! =null){ ListNode temp = cur.next; Next = first.next; first.next = cur; cur=temp; //whileThe last line in the loop is to move the pointer cur}returnfirst.next; // first is the first element (val = -1)}}Copy the code

class Solution {
    public ListNode reverseList(ListNode head) {
      ListNode cur=head;
      ListNode pre=null;
      while(cur! =null){ ListNode temp = cur.next; Cur ->next cur.next = pre; // Update the pre and cur Pointers pre=cur; // Update the pre and cur Pointers pre=cur; cur = temp; //whileThe last line in the loop is to move the pointer cur}returnpre; }}Copy the code

151, Reverse the words in the string (Spaces are words, so Spaces must be recognized)

Solution (calling the underlying static method)

class Solution { public String reverseWords(String s) { s=s.trim(); List List = arrays.asList (s.split("\\s+")); // A static method of the array class that takes an array and returns list collections.reverse (list); // A static method of the Collection class that takes list and returns listreturn String.join("",list); // Static method of the String class, taking list and returning String}}Copy the code

The four functions are expressed in their own code (in effect, they are copied from the source code)

As follows: