Algorithm|LinkedList

基本思想

链表的题目，有一个最基本的思想：

如果感觉针对头或者尾需要特殊处理操作的时候, 可以新建一个 dummy node, 不包含任何实际操作，但是可以让算法执行更流畅更通用

快慢指针

判断环

141.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。

注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true, 否则，返回 false

第一思路：存储访问Map

第一眼想到的是用一个Map存储是否已经访问的状态

在一次遍历的过程中更新这个Map

如果存在环，那么一定会再次访问Map中相同的节点，这个时候就可以以此来进行判断了

public boolean hasCycle(ListNode head) {
   if (head == null) {
      return false;
   }
   Map<ListNode, Boolean> visited = new HashMap<>();
   ListNode curr = head;
   while (curr.next != null) {
      if (Boolean.TRUE.equals(visited.get(curr))) {
         return true;
      }
      visited.put(curr, true);
      curr = curr.next;
   }
   return false;
}

进阶思路：快慢指针

这是经典的Floyd判圈算法，原理很简单：我们手动设定两个指针，一快一慢，如果存在环，那么一定会有某个时刻，快的重新追上慢的

原理虽然简单，但是带来的效果很强大，他解决了我们第一种情况下O(n)空间复杂度的问题，只实现了常量级（O(2)）的内存，就实现了一样的效果

/**
 * 快慢指针Floyd判圈算法
 * @param head 头结点
 * @return 是否有环
 */
public boolean floydCircleCheck(ListNode head) {
   //0个节点或者是1个节点都可以认为没有环
   if (head == null || head.next == null) {
      return false;
   }
   ListNode slow = head;
   ListNode fast = head.next;
   while (slow != fast) {
      //如果没有环，fast一定走到了终点           
      if (fast == null || fast.next == null) {
         return false;
      }
      slow = slow.next;
      fast = fast.next.next;
   }
   //有环，快的一定会在某一轮次追上慢的
   return true;
}

双指针

反转链表

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

第一思路：双指针

一次遍历，反转next域，最后返回尾节点

public ListNode reverseList (ListNode head) {
   if (head == null) {
      return null;
   }
   if (head.next == null) {
      return head;
   }
   ListNode slow = head;
   ListNode fast = slow.next;
   slow.next = null;
   while (fast != null) {
      ListNode next = fast.next;
      fast.next = slow;
      slow = fast;
      fast = next;
   }
   return slow;
}

需要注意，初始的时候需要设置头节点（也就是反转后的尾节点）next域 = null 以通过 OJ 测试案例

进阶思路：递归

虽然双指针的解法空间复杂度更优，递归的是O(n)，但是递归的写法更能体现思维能力

protected ListNode reverseAllFollow(ListNode head) {
   //空或是一个元素时无需反转
   if (head == null || head.next == null) {
      return head;
   }
   ListNode next = head.next;
   ListNode newHead = reverseAllFollow(next);
   next.next = head;
   return newHead;
}

public ListNode reverseList(ListNode head) {
   if (head == null) {
      return null;
   }
   ListNode tail = reverseAllFollow(head);
   head.next = null;
   return tail;
}