Linked List Cycle

Algorithms
linked list
Catalogue
  1. 1. 141. Linked List Cycle
    1. 1.1. Sol1. HashSet
    2. 1.2. Sol2. 快慢指针
  2. 2. 142. Linked List Cycle II
    1. 2.1. Sol1. HashSet
    2. 2.2. Sol2. 快慢指针
  3. 3. 287. Find the Duplicate Number
  4. 4. 160. Intersection of Two Linked Lists
    1. 4.1. Sol1. HashSet
    2. 4.2. Sol2. Two Pointer
  • 单链表检测是否有环，如果有，返回环交点。
  • 这种题主要考察这个知识点作为一种common sense是否了解了，如果没做过这类题型恐怕很难想到空间最优的快慢指针解法！

141. Linked List Cycle

单链表求是否存在环？

Sol1. HashSet

1
2
3
4
5
6
7
8
9
10
# 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

Sol2. 快慢指针

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

1
2
3
4
5
6
7
8
9
10
# 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

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

Sol1. HashSet

1
2
3
4
5
6
7
8
9
10
# 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

Sol2. 快慢指针

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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));
  • 但是又要求 Time : O(n), Space : O(1), Input Array Read only，只能考虑其他解法！
  • (比较难想到)Array里index, value中把value当作”next”的index，就可以把问题转化成了Linked List II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Time : O(n), Space : O(1)
class Solution(object):
    def findDuplicate(self, nums):
        if not nums: return 0
        slow = fast = nums[0] # Start from index 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

Sol1. HashSet

  • 挺喜欢这种解法，简单易懂，but空间复杂度略高，会让你优化空间！
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 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

Sol2. Two Pointer

  • 这个解法灰常魔幻，不管有没有intersection都成立
  • 链表走到tail了就去另一个链表，不相交那么会在None点走到
  • 充分利用了两个链表的长度特性
1
2
3
4
5
6
7
8
9
10
11
# 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
Share