Cycle in Linked List

Easy

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next


def has_cycle(head):

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

  while True:

    if slow is None or fast is None:
      return False

    if slow.value == fast.value:
      return True

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

To get the length of a cycle, first find the node where the pointers meet as above. Save that node. Then keep going next while iterating a counter until you reach that same node again.

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next


def find_cycle_length(head):
  slow, fast = head, head
  while fast is not None and fast.next is not None:
    fast = fast.next.next
    slow = slow.next
    if slow == fast:  # found the cycle
      return calculate_cycle_length(slow)

  return 0


def calculate_cycle_length(slow):
  current = slow
  cycle_length = 0
  while True:
    current = current.next
    cycle_length += 1
    if current == slow:
      break
  return cycle_length

Find Start of Cycle

First, find the length of the cycle K like above. Then, with two new pointers p1 and p2, move one of them (p2) ahead K nodes. Next, increment p1 and p2 in a loop until they are the same. This will be the start of the cycle.

def find_cycle_length(slow):
  cycleLength = 0

  p = slow

  while True:
    p = p.next
    cycleLength += 1
    if p == slow:
      break
  
  return cycleLength


def find_cycle_start(head):
  fast = head
  slow = head

  while fast is not None and slow is not None:
    fast = fast.next.next
    slow = slow.next

    if fast == slow:
      break
    
  cycleLength = find_cycle_length(slow)

  p1 = head
  p2 = head

  for _ in range(cycleLength):
    p2 = p2.next
  
  while p1 is not p2:
    p1 = p1.next
    p2 = p2.next
  
  return p1

Happy Number

Square sum of a number's digits either loops or goes to 1. Use fast and slow pointer method to check if looping. If looped, check if value is 1 to determine if happy number or not

def find_cycle_length(slow):
  cycleLength = 0

  p = slow

  while True:
    p = p.next
    cycleLength += 1
    if p == slow:
      break
  
  return cycleLength


def find_cycle_start(head):
  fast = head
  slow = head

  while fast is not None and slow is not None:
    fast = fast.next.next
    slow = slow.next

    if fast == slow:
      break
    
  cycleLength = find_cycle_length(slow)

  p1 = head
  p2 = head

  for _ in range(cycleLength):
    p2 = p2.next
  
  while p1 is not p2:
    p1 = p1.next
    p2 = p2.next
  
  return p1

Middle of the Linked List

Just use a fast and slow pointer. When fast pointer finishes, slow pointer points to middle.

def find_middle_of_linked_list(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

  return slow

Palindrome Linked List

def reverse(head):
  prev = None

  while head is not None:
    next = head.next
    head.next = prev
    prev = head
    head = next

  return prev

def printList(head):
  copy = head
  while copy is not None:
    print(copy.value, end=" -> ")
    copy = copy.next
  print("None")
  return

def is_palindromic_linked_list(head):

  slow, fast = head, head
  isPalindrome = True

  # Find middle
  while fast is not None and fast.next is not None:
    fast = fast.next.next
    slow = slow.next


  # Reverse Second Half
  reversed_head = reverse(slow)
  reversed_head_copy = reversed_head
  
  #Compare First half with reversed second half
  while reversed_head is not None and head is not None:

    if head.value != reversed_head.value:
      isPalindrome = False

    reversed_head = reversed_head.next
    head = head.next

  # Reverse it back
  reverse(reversed_head_copy)

  return isPalindrome

Rearrange Linked List

Use above to find middle of linked list and reverse the second half of the linked list. Then iterate through the lists to interleave them together.

def reverse(head):
  prev = None
  while head is not None:
    next = head.next
    head.next = prev
    prev = head
    head = next
  return prev

def reorder(head):

  fast, slow = head, head

  # Find middle of Linked List
  while fast is not None and fast.next is not None:
    fast = fast.next.next
    slow = slow.next

  sec_half_head = reverse(slow)
  head_first_half = head

  #printList(sec_half_head)

  while head_first_half is not None and sec_half_head is not None:
    temp = head_first_half.next
    head_first_half.next = sec_half_head
    head_first_half = temp

    temp = sec_half_head.next
    sec_half_head.next = head_first_half
    sec_half_head = temp

  if head_first_half is not None:
    head_first_half.next = None

  return

Cycle in Circular Array

Solution is not too difficult. For this we check if there is a loop starting from each index from 0 to len(arr). Just like normal, loop is when slow = fast at some point. The only other checks we have, is we need to make sure the direction of each index is the same as the starting one. Can improve time complexity to O(n), by keeping track of visited indices. Can probably do this with dictionary where `d[index] = 1 for visited.

def next_index(arr, idx, direction):

  if direction != (arr[idx] >= 0):
    return -1

  next_index = (idx + arr[idx]) % len(arr)

  if next_index == idx:
    return -1

  return next_index
 
def circular_array_loop_exists(arr):

  # Loop through Each Index with Fast and Slow
  # Pointers to check if loop.

  for i in range(len(arr)):
    slow = i
    fast = i

    # Positive is forward, Negtive is backward
    direction = arr[i] >= 0

    while True:

      slow = next_index(arr, slow, direction)
      fast = next_index(arr, fast, direction)
      fast = next_index(arr, fast, direction)

      if slow == -1 or fast == -1 or slow == fast:
        break

    if slow != -1 and slow == fast:
      return True
  
  return False