## Problems

### Reverse list

Hypothesis approach

• Assume the function `solve(head)` reverse’s the list with `head` marking start of the list.
• Next, check for smaller input. In this case, smaller input refers to list starting with `head.next`.
• Next, identify the relationship between the two functions.
``````orig_input = 1 -> 2 -> 3
smaller_input = 2 -> 3

solve(smaller_input) = 3 -> 2

solve(orig_input) = solve(smaller_input) + add '1' to the end``````
• Base case is empty list.
``````def solve(head):

prev = None
# need to store next element for reference

# do the swap

# move pointer

return prev``````

### Check if list is palindrome

``````def solve(head):
return

prev = None
while fast_pointer and fast_pointer.next:
fast_pointer = fast_pointer.next.next

# Reverse the first half of the list
next_node = pointer.next
pointer.next = prev
prev = pointer
pointer = next_node

# prev = first half of the list (reversed)
# pointer = second half od the list

# Handle odd length (as pointer is at center)
if fast_pointer:
pointer = pointer.next

is_palindrome = True
while pointer:
if prev.val != pointer.val:
is_palindrome = False
break

prev = prev.next
pointer = pointer.next

return is_palindrome``````

### Remove all occurances of val

``````def solve(head, val):
prev = None
if prev:
# delete the node, prev remains the same
else:
# handle the case where val is the first node
else:
# just move to the next node

return root``````

You can only use `node.printValue()` and `node.getNext()` methods, and have to print the linked list in reverse order.

``````# Time = O(n^2), Space = O(1)
# Get length of list
length = 0
while node:
length += 1
node = node.getNext()

# Iterate to length and print the last node and repeat with length - 1
while length > 0:

for _ in range(length - 1):
node = node.getNext()
node.printValue()

length -= 1``````
``````# Time = O(n), Space = O(sqrt(n))
# Get length of list
length = 0
while node:
length += 1
node = node.getNext()

# Use SQRT decomposition to store sqrt(n) size blocks and print them in reverse
length_sqrt = math.floor(math.sqrt(length)) # floor/ceil does not matter
while length > 0:

orig_length = length
length = max(0, length - length_sqrt)

for _ in range(length):
node = node.getNext()

# Create block of size sqrt(n)
block = []
for _ in range(length, orig_length):
block.append(node)
node = node.getNext()

# Print block in reverse
for i in range(len(block)-1, -1, -1):
block[i].printValue()``````
``````# Time = O(n logn), Space = O(logn)

# Use divide and conquer (similar to merge sort). Print the right value before left value
def helper(start_node, end_node):
if start_node is None or start_node == end_node:
return

if start_node.getNext() == end_node:
start_node.printValue()
return

# Use two slow/fast pointer to find the middle of the list
slow = start_node
fast = start_node

while fast != end_node and fast.getNext() != end_node:
slow = slow.getNext()
fast = fast.getNext().getNext()

# Call the function first with right side, and then left side
helper(slow, end_node)
helper(start_node, slow)``````