Two Pointers

2023-05-04
#python
Data Structure & Algorithm

A generalized view of “Two Pointers”, IMO

  • slow, fast pointers in the linked list problems
    • LeetCode 234. Palindrome Linked List. Given the head of a singly linked list, return true if it is a palindrome or false otherwise. 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      def isPalindrome(self, head: Optional[ListNode]) -> bool:
          slow, fast= head, head
          while fast and fast.next:
              slow, fast = slow.next, fast.next.next
          # Be careful on the ordering of the following 3 lines, need to run "prev.next = None" after "slow=slow.next", otherwise, output is wrong; I think the reason is that prev and slow are pointers that pointed to the same object.
          prev = slow
          slow = slow.next
          prev.next = None

          while slow:
              # slow.next, prev, slow = prev, slow, slow.next
              tmp = slow.next
              slow.next = prev
              prev = slow
              slow = tmp
          fast, slow = head, prev
          while slow:
              if fast.val != slow.val:
              	return False
              fast, slow = fast.next, slow.next
          return True
  • left, right pointers in array represented problems