Detect Cycle

• 单链表检测是否有环，如果有，返回环交点。
• 这种题主要考察这个知识点作为一种common sense是否了解了，如果没做过这类题型恐怕很难想到空间最优的快慢指针解法！

141. Linked List Cycle

单链表求是否存在环？

• 解法1. HashSet

  # Time : O(n), Space : O(n)
  class Solution(object):
    def hasCycle(self, head):
        visited = set()
        while head:
            if head in visited:
                return True
            visited.add(head)
            head = head.next
        return False
  

• 解法2. 快慢指针

小trick : 如果有环，快指针一定会追上慢指针

# Time : O(n), Space : O(1)
class Solution(object):
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

142. Linked List Cycle II

单链表是否存在环，如果存在返回环交点

• 解法1. HashSet

  # Time : O(n), Space : O(n)
  class Solution(object):
    def detectCycle(self, head):
        visited = set()
        while head:
            if head in visited:
                return head
            visited.add(head)
            head = head.next
        return None
  

• 解法2. 快慢指针

小trick : 关于长度的证明，相遇点到交点的距离=起点到交点的距离！

# Time : O(n), Space : O(1)
class Solution(object):
    def detectCycle(self, head):
        if not head: return None
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast: # Detect Cycle
                fast = head
                while slow != fast:
                    fast = fast.next
                    slow = slow.next
                return fast
        return None

287. Find the Duplicate Number

• 这道题显然可以解1.HashSet(T:O(n),S:O(n)),解2. Sort(T:O(nlogn),S:O(1));但是又要求时间是O(n),空间是O(1)，只能考虑其他解法！
• Array里index, value中把value当作"next"的index，就可以把问题转化成了Linked List II(比较难想到)

  # Time : O(n), Space : O(1)
  class Solution(object):
    def findDuplicate(self, nums):
        if not nums: return 0
        slow = fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        fast = nums[0]
        while fast != slow:
            fast = nums[fast]
            slow = nums[slow]
        return fast
  

  160. Intersection of Two Linked Lists

• 解法1 HashSet

  • 挺喜欢这种解法，简单易懂，but空间复杂度略高，会让你优化空间！

    # Time : O(m+n), Space : O(m)
    class Solution(object):
    def getIntersectionNode(self, headA, headB):
      visited = set()
      while headA:
          visited.add(headA)
          headA = headA.next
    
      while headB:
          if headB in visited:
              return headB
          headB = headB.next
      return None
    

• 解法2 Two Pointer
  • 这个解法灰常魔幻，不管有没有intersection都成立
  • 链表走到tail了就去另一个链表，不相交那么会在None点走到
  • 充分利用了两个链表的长度特性

# Time : O(m+n), Space : O(1)
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        if not headA or not headB:
            return None

        pA, pB = headA, headB
        while pA is not pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA
        return pA