CodingBat

  • Go to (CodingBat.com)[https://www.codingbat.com/python] and create an accoutn and log into the website.
  • Start to solve problems. If you are new, the Warmup-1 is a good place to start.
  • Let’s solve problems in the CodingBat.com website for 45 minutes.

Review of LeetCode

  • Daily practice
  • Have a break
  • Revisit a problem and solve again

Review of Linked List

HackerRank video

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

Hackerrank problems

def printLinkedList(head):
    tmp = head
    while tmp:
        print(tmp.data)
        tmp = tmp.next

Insert a node at the head of a linked list

def insertNodeAtHead(llist, data):
    # Write your code here
    new_node = SinglyLinkedList()
    new_node.data = data
    new_node.next = None

    if not llist:
        llist = new_node
        return llist
    new_node.next = llist
    llist = new_node
    return llist

Reverse a linked list

def reverse(head):
    cur, prev, next = head, None, None
    while cur:
        next = cur.next
        cur.next = prev
        prev = cur
        cur = next
    return prev

Practice

Compare two linked list

def compare_lists(llist1, llist2):
    if not llist1 and not llist2:
        return True
    while llist1 or llist2:
        if not llist1 or not llist2:
            return False
        if llist1.data != llist2.data:
            return False
        llist1 = llist1.next ; llist2 = llist2.next
    return True

Solutions

- https://leetcode.com/problems/middle-of-the-linked-list
Approach 1: Find the length
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        def findLength(head):
            cnt = 0
            cur = head
            while cur:
                cnt += 1
                cur = cur.next
            return cnt
        
        cur = head
        mid = findLength(head) // 2
        while mid > 0:
            cur = cur.next
            mid -= 1
        return cur
Approach 2: Turtle and Rabbit (Tortoise and Hare)
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Explore - Linked List Cycle

Linked List Cycle

Approach 1 - Hash Table


class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        seen = set()
        cur = head
        while cur:
            if cur in seen:
                return True
            seen.add(cur)
            cur = cur.next
        return False

Approach 2 - Two Poiners


class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = fast = head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False
Written on