例题1-链表是否存在环

解法1：双指针-空间复杂度常数项
解法2：哈希表记录已经出现过的节点，观察是否具有重复节点出现
image.png
image.png

  1. public class Solution {
  2.     public boolean hasCycle(ListNode head) {
  3.         if (head == null || head.next == null) {
  4.             return false;
  5.         }
  6.         ListNode slow = head;
  7.         ListNode fast = head.next;
  8.         while (slow != fast) {
  9.             if (fast == null || fast.next == null) {
  10.                 return false;
  11.             }
  12.             slow = slow.next;
  13.             fast = fast.next.next;
  14.         }
  15.         return true;
  16.     }
  17. }
  1. public class Solution {
  2.     public boolean hasCycle(ListNode head) {
  3.         Set<ListNode> seen = new HashSet<ListNode>();
  4.         while (head != null) {
  5.             if (!seen.add(head)) {
  6.                 return true;
  7.             }
  8.             head = head.next;
  9.         }
  10.         return false;
  11.     }
  12. }

例题2-快速排序

快速排序