Chapter 1 - Lists and Recursion

This chapter heavily focuses on graph and recursion, however there is another chapter that talks more about graph so we will only dive into recursion. On the homework there is also some linked list.

Basic Linked List Traversal

I have two linked lists Y and M, for every element in Y, I want to prepend it in front of M

while Y:
    temp = Y.next
    Y.next = M
    M = Y
    Y = temp

Linked list reversal on Y

previous = ListNode() # Create a new listnode to store the previous value
previous.next = Y # init with the head of Y
while Y:
    temp = Y.next # store the next value of Y to temp
    Y.next = previous # redirect the pointer of Y.next so it points to previous
    previous = Y # store the current Y to previous for the next iteration
    Y = temp # update the current pointer to point at temp which is the next origin value of Y
Y = previous # resetting pointer back to the beginning of the list
return Y
    

• 206. Reverse Linked List - My Solution

• 92. Reverse Linked List II - My Solution

• 2074. Reverse Nodes in Even Length Groups - My Solution

Linked List Cycle Detection

We can use the tortoise and hare algorithm also known as Floyd's algorithm to approach this. Let's initialize two pointer call fast and slow, fast will move twice as fast as the slow pointer, and if the fast pointer catches up to the slow pointer before it reaches the end, we know there is a cycle.

slow = Y
fast = Y
while fast.next and fast.next.next:
    if slow == fast:
        return True
    slow = slow.next
    fast = fast.next.next
return False

• 141. Linked List Cycle - My Solution

• 142. Linked List Cycle II - My Solution

• 287. Find the Duplicate Number - My Solution

Recursion and Tower of Hanoi

Basic ToH Solver

def ToH (n, a, b, c):
    if n == 1:
        print(f"moving ring {n} from {a}, {b}")
    ToH(n-1, a, c, b)
    print(f"moving ring {n} from {a}, {b}")
    ToH(n-1, c, b, a)
# a = start, b = end, c = aux
ToH(3, "a", "b", "c") 

Circular ToH Solver

Circular ToH is a concept that you can only move ring n either from the operation of a to b, b to c, or c to a. We can simply just mimic the operation on the actual code (literally!)

def ToH (n, a, b, c):
    if n == 1:
        print(f"moving ring {n} from {a}, {b}")
    ToH(n-1, a, b, c)
    ToH(n-1, b, c, a)
    print(f"moving ring {n} from {a}, {b}")
    ToH(n-1, c, a, b)
    ToH(n-1, a, b, c)
# a = start, b = end, c = aux
ToH(3, "a", "b", "c") 

Why is only 1 print statement and in between ToH(n-1, b, c, a) and ToH(n-1, c, a, b)? Because consider whne n = 2, in order for the largest disk 1 to be moved to b, we need 2 to be on c. Moving n=2 from a to b, b to c counts as one operation, because of the problem constraint, after moving n=1 to b we have to move n=2 from c to a and a to b, which counts as another operation.

Imagine all the disks have two colors, red and white. Initally, all disks are facing up which is red, after the ToH operation what's their color? (facing up or down?)

Because of the uniqueness of our recursive call, we are guaranteed to know every disk will have at least 2^(n-1) operation count, if moving a disk one time will make it flip the other way, moving a disk twice can make it flip back to the original way. So every disk except the largest disk will still be facing up due to the 2^n operation count which is red and the largest/bottom disk will have 1 operation to make it white. If we have n=2, the first disk will have 2^1 = 2, and second disk will have 2^0 = 1 (refer to 2^(n-1))

How to have every disk appear as white?

Make the operation a multiple of 3!

def ToH (n, a, b, c):
    if n == 1:
        print(f"moving ring {n} from {a}, {b}")
    ToH(n-1, a, c, b)
    print(f"moving ring {n} from {a}, {b}")
    ToH(n-1, c, b, a)
    ToH(n-1, a, b, c)
# a = start, b = end, c = aux
ToH(3, "a", "b", "c") 

How to have every disk appear as red?

The original ToH would put every disk to red except the bottom disk due to 2^0 = 1. We just have to double that operation so that 2^0 + 2^0 = 2. This would not affect other disks because an even number + even number is still an even number.

We can simply move everything to the aux pole, then move everything from aux pole to dest pole

def ToH (n, a, b, c):
    if n == 1:
        print(f"moving ring {n} from {a}, {b}")
    ToH(n-1, a, c, b)
    print(f"moving ring {n} from {a}, {b}")
    ToH(n-1, c, b, a)
# a = start, b = end, c = aux
ToH(3, "a", "c", "b")
ToH(3, "c", "b", "a")