判定链表中是否含有环

• 思路：使用两个指针，快指针每次前进两步，慢指针每次前进一步。当快指针和慢指针相遇时，若相遇位置在链表内部，则链表含有环。
• 实现：

  public boolean hasCycle(ListNode head) {
      ListNode fast, slow;
      fast = slow = head;
      while (fast != null && fast.next != null) {
          fast = fast.next.next;
          slow = slow.next;
          if (fast == slow) {
              return true;
          }
      }
      return false;
  }

已知链表含有环，返回环的起始位置

• 思路：当快慢指针相遇时，重新让其中一个指针回到头节点，保持两个指针以相同速度前进，相遇点即为环起始位置。
• 实现：

  public ListNode detectCycle(ListNode head) {
      ListNode fast, slow;
      fast = slow = head;
      while (fast != null && fast.next != null) {
          fast = fast.next.next;
          slow = slow.next;
      }
      slow = head;
      while (slow != fast) {
          fast = fast.next;
          slow = slow.next;
      }
      return slow;
  }

寻找链表的中点

• 思路：让快指针每次前进两步，慢指针每次前进一步。当快指针到达链表末尾时，慢指针即为中点。
• 实现：

  public ListNode findMiddle(ListNode head) {
      ListNode slow, fast;
      slow = fast = head;
      while (fast != null && fast.next != null) {
          fast = fast.next.next;
          slow = slow.next;
      }
      return slow;
  }

寻找链表的倒数第k个元素

• 思路：让快指针先行k步，然后让两个指针以相同速度前进，当快指针到达末尾时，慢指针的位置即为目标元素。
• 实现：

  public ListNode kthNode(ListNode head, int k) {
      ListNode slow, fast;
      slow = fast = head;
      while (k-- > 0 && fast != null) {
          fast = fast.next;
      }
      while (fast != null) {
          slow = slow.next;
          fast = fast.next;
      }
      return slow;
  }

二分查找

• 思路：初始化左右指针，分别表示数组的起始和结束位置，通过中间值比较目标值的位置，逐步缩小搜索范围。
• 实现：

  public int searchInsert(int[] nums, int target) {
      int n = nums.length;
      int left = 0;
      int right = n - 1;
      while (left <= right) {
          int middle = left + ((right - left) / 2);
          if (nums[middle] > target) {
              right = middle - 1;
          } else if (nums[middle] < target) {
              left = middle + 1;
          } else {
              return middle;
          }
      }
      return -1;
  }

两数之和

• 思路：使用左右指针调整和，找到满足条件的数对。
• 实现：

  public int[] twoSum(int[] nums, int target) {
      int left = 0, right = nums.length - 1;
      while (left < right) {
          int currentSum = nums[left] + nums[right];
          if (currentSum == target) {
              return new int[]{nums[left], nums[right]};
          } else if (currentSum < target) {
              left++;
          } else {
              right--;
          }
      }
      return new int[0];
  }

反转数组

• 思路：使用左右指针交换元素，直到左右指针相遇。
• 实现：

  void reverseArray(int[] nums) {
      int left = 0, right = nums.length - 1;
      while (left < right) {
          int temp = nums[left];
          nums[left] = nums[right];
          nums[right] = temp;
          left++;
          right--;
      }
  }

滑动窗口算法

• 思路：维护一个窗口，记录字符频率，调整窗口大小以满足条件。
• 实现：

  void slidingWindow(String s, String t) {
      Map
        
          need = new HashMap<>();
      Map
         
           window = new HashMap<>();
      for (char ch : t.toCharArray()) {
          need.put(ch, need.getOrDefault(ch, 0) + 1);
      }
      int left = 0, right = 0;
      int valid = 0;
      while (right < s.length()) {
          char c = s.charAt(right);
          if (c != t.charAt(right)) {
              right++;
              continue;
          }
          right++;
          while (valid < t.length() && window.size() > need.size()) {
              char d = s.charAt(left);
              if (d == t.charAt(left)) {
                  valid--;
              }
              window.put(d, window.getOrDefault(d, 0) - 1);
              if (window.get(d, 0) == 0) {
                  window.remove(d);
              }
              left++;
          }
          if (valid == t.length()) {
              return true;
          }
      }
      return false;
  }