[Leetcode] Two Pointers in Fast & Slow Problems

Floyd’s Tortoise and Hare Problem

141. Linked List Cycle

Leetcode: https://leetcode.com/problems/linked-list-cycle/description/

Solution 1:

Use fast & Slow two pointers, if a linkedlist has circle, the fast will finally meet with the slow pointer in the cycle

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
      return false;
    }
    ListNode slow = head, fast = head.next.next;
    while (fast != null && fast.next != null) {
        if (slow == fast) {
            return true;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    return false;
}

def hasCycle(self, head):
    if not head:
        return False
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if fast == slow:
            return True
    return False

Solution 2:

Recursive solution, mark all the visited node (pointing to itself), if meet a node that pointing to itself, then there is a cycle

public boolean hasCycle(ListNode head) {
  if (head == null || head.next == null) return false;
  if (head.next == head) return true;
  ListNode nextNode = head.next;
  head.next = head; // pointing visited node to itself, so that we can know there's a loop if it points to itself
  boolean isCycle = hasCycle(nextNode);
  return isCycle;
}

142. Linked List Cycle II

Leetcode: https://leetcode.com/problems/linked-list-cycle-ii/description/

Video: https://www.youtube.com/watch?v=-YiQZi3mLq0

[Solution]

def detectCycle(self, head):
    if not head:
        return head
    slow, fast = head, head
    ptr1, ptr2 = head, None
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            ptr2 = slow
            break
    ptr1 = head
    while ptr1 and ptr2 and ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next
    return ptr2

287. Find the Duplicate Number

Leetcode: https://leetcode.com/problems/find-the-duplicate-number/description/
Solution: https://leetcode.com/problems/find-the-duplicate-number/solution/

[Solution] Similar to cycle in the linked list. See details above.

1. We are sure that there’s duplicate in the array: there’s a cycle
2. Difference with the cycle list: next node i+1 is represented as nums[nums[i]]. Thus, slow runner is nums[nums[i]], fast runner is nums[nums[nums[i]]]
3. Find the intersection of two runners first
4. Find the entrance of the cycle, the entrance is the duplicate number

class Solution {
    public int findDuplicate(int[] nums) {
        // Find the intersection point of the two runners.
        int tortoise = nums[0];
        int hare = nums[0];
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);

        // Find the "entrance" to the cycle.
        int ptr1 = nums[0];
        int ptr2 = tortoise;
        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }

        return ptr1;
    }
}

Find Point Problem

109. Convert Sorted List to Binary Search Tree

Leetcode: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/

[Solution]

1. Use fast and slow pointers to find the middle point of the linked list

fast = fast.next.next
slow = slow.next

1. The fast pointer actually become useless after finding the middle point

2. After we find the middle node (after fast reach to the end), we split the linked list to left sublist (that’s why I used a prevSlow pointer, since we need to cut the list off at the middle pointer in order to use the left sublist!) and right sublist, which would also be the left subtree and right subtree.

   [-10,-3,0,5,9]
           ^   ^
         slow  fast
         middle
   
   left: [-10,-3]
   right: [5,9]

3. Then we repeat the 1,2,3 steps until we finish the whole list

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        return helper(head);
    }

    private TreeNode helper(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);

        ListNode slow = head;
        ListNode preSlow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {
            preSlow = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        preSlow.next = null;
        TreeNode root = new TreeNode(slow.val);
        root.left = helper(head);
        root.right = helper(slow.next);
        return root;
    }
}

109. Convert Sorted List to Binary Search Tree

Leetcode: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/

[Solution]

1. Use fast and slow pointers to find the middle point of the linked list

fast = fast.next.next
slow = slow.next

1. The fast pointer actually become useless after finding the middle point

2. After we find the middle node (after fast reach to the end), we split the linked list to left sublist (that’s why I used a prevSlow pointer, since we need to cut the list off at the middle pointer in order to use the left sublist!) and right sublist, which would also be the left subtree and right subtree.

   [-10,-3,0,5,9]
           ^   ^
         slow  fast
         middle
   
   left: [-10,-3]
   right: [5,9]

3. Then we repeat the 1,2,3 steps until we finish the whole list

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        return helper(head);
    }

    private TreeNode helper(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);

        ListNode slow = head;
        ListNode preSlow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {
            preSlow = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        preSlow.next = null;
        TreeNode root = new TreeNode(slow.val);
        root.left = helper(head);
        root.right = helper(slow.next);
        return root;
    }
}

61. Rotate List

Leetcode: https://leetcode.com/problems/rotate-list/

Note:

1. Use two pointers l, and r with a distance of k
2. Beware of the cases where k > len(list) and k == len(list)
3. If we don’t want to count the length of the whole list, we could set r to head everytime it hits the end. But that would lead to TLE when k is very large.

def rotateRight(self, head, k):
    if not head or not k:
        return head
    l, r, cur = head, head
    length = 0
    while cur:
        cur = cur.next
        length += 1

    k %= length

    if k == 0:
        return head

    while k:
        r = r.next
        k -= 1

    prev = r
    while r:
        end = l
        l = l.next
        prev = r
        r = r.next
    prev.next = head
    end.next = None
    return l

Odd & Even Pointers

328. Odd Even Linked List

Leetcode: https://leetcode.com/problems/odd-even-linked-list/

Note: Use two pointers odd and even to track odd and even nodes.

def oddEvenList(self, head: ListNode) -> ListNode:
    if not head:
        return 
    if not head.next:
        return head
    head_odd, odd = head, head
    head_even, even = head.next, head.next
    prev = None
    while odd and even:
        odd.next = even.next
        prev = odd
        odd = odd.next
        if odd: # !!!
            even.next = odd.next
            even = even.next
    if odd:
        odd.next = head_even
    elif prev:
        prev.next = head_even
    return head_odd