1、原地移除元素

数组原地移除元素，且空间复杂度为O(1) ，可以直接使用快慢指针

  • 快慢指针都以0 开始增加
  • 快指针直接递增，慢指针在nums[slow]!=nums[fast] 时递增，这样就可以保证慢指针的记录的值仅包含非目标值。
  • 返回慢指针，可以看作返回长度为 slow的数组。
  1.     public int removeElement(int[] nums, int val) {
  2.         int slow = 0, fast;
  3.         for (fast = 0; fast < nums.length; fast++) {
  4.             if (nums[fast] != val) {
  5.                 nums[slow] = nums[fast];
  6.                 slow++;
  7.             }
  8.         }
  9.         return slow;
  10.     }

2、反转字符串中的单词

  1. class Solution {
  2.     public String reverseWords(String s) {
  3.         //直接在字符串首位加空格，方便判断
  4.         s = " " + s;
  5.         int n = s.length();
  6.         StringBuilder sb = new StringBuilder();
  7.         int left, right;
  8.         //left 一直在往左边走
  9.         for (left = n - 1, right = n; left >= 0; left--) {
  10.             char ch = s.charAt(left);
  11.             //如果遇到空格
  12.             if (ch == ' ') {
  13.                 //将截取的字符串加入到结果中
  14.                 if (left + 1 < right) {
  15.                     sb.append(s, left + 1, right).append(' ');
  16.                 }
  17.                 //移动右指针
  18.                 right = left;
  19.             }
  20.         }
  21.         return sb.substring(0, sb.length() - 1);
  22.     }
  23. }

3、环形链表

选取快慢指针，快指针走两步，慢指针走一步，如果有环，必定相遇 设链表非环部分长度为 a , 环中部分长度为 b ，f = 2s 且fast总比slow多走n个环，所以 f = s + nb 由上得：f = 2nb s = nb 此时将f 指向头节点，slow 与 fast 同时每轮向前走1 步 当 f 走到a 点时，s = nb+a 此时两指针重合，并指向入口

  1.     public ListNode detectCycle(ListNode head) {
  2.         ListNode slow = head, fast = slow;
  3.         while (slow.next != null && fast.next != null) {
  4.             slow = slow.next;
  5.             fast = fast.next.next;
  6.             if (fast == slow) {
  7.                 ListNode index1 = head;
  8.                 ListNode index2 = fast;
  9.                 while (index2 != index1) {
  10.                     index2 = index2.next;
  11.                     index1 = index1.next;
  12.                 }
  13.                 return index1;
  14.             }
  15.         }
  16.         return null;
  17.     }