link_list.py

# hints from http://wuchong.me/blog/2014/03/25/interview-link-questions/

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


class LinkList:
    def __init__(self, values):
        self.head = Node(None)
        p = self.head
        for v in values:
            node = Node(v)
            p.next = node
            p = p.next

    def display(self):
        p = self.head
        while p.next:
            p = p.next
            print(p.value, end=' -> ')
        print('None')


def delete_node(link, node):
    """
    delete the node in link list in O(1)

    solution: replace value and delete next node if node is not the last one.
    """
    assert node is not None
    assert node.next is not None

    p = node.next
    node.value = p.value
    node.next = p.next
    del p


def reverse_link(head):
    """
    link list with head, use 3 pointers to reverse it
    """
    if head.next is None:
        return head

    cur = head.next
    nxt = pre = None
    while cur:
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt

    head.next = pre
    return head


def last_k_node(head, k):
    """
    use 2 pointers with distance = k
    """
    assert k >= 0

    slow = fast = head
    while k > 0:
        if fast is None:
            return None
        fast = fast.next
        k -= 1

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

    return slow.value


def middle_node(head):
    """
    use 2 pointers with v and 2 * v
    """
    if head.next is None:
        return None

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

    return slow.value


def has_circle(head):
    """
    use 2 pointers with v and 2 * v
    """
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if slow == fast:
            return True

    return False


def entrance_of_circle(head):
    """
    set fast_dist = l1, slow_dist = l2, circle = l, meet_after_entrance = m
    l2 = dist + m
    l1 = dist + m + k * l = 2 * l2
    dist + m = k * l
    """
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if slow == fast:
            break

    if slow != fast:
        return None

    fast = head
    while fast != slow:
        fast = fast.next
        slow = slow.next

    return fast.value


def has_intersect(x, y):
    """
    tails are the same if they have intersections
    """
    if not (x.head.next and y.head.next):
        return None

    x_end = x.head
    while x_end.next:
        x_end = x_end.next

    y_end = y.head
    while y_end.next:
        y_end = y_end.next

    return x_end == y_end


def has_intersect_with_circle(x, y):
    """
    find two tails, walk on the circle
    """
    def circle(head):
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                return slow
        return None

    cx, cy = circle(x.head), circle(y.head)
    if not (cx and cy):
        return None

    if cx == cy:
        return True

    p = cx.next
    while p != cx:
        if p == cy:
            return True
        p = p.next

    return False


def first_common_node(x, y):
    """
    Tail alignment.
    """
    def get_length(head):
        p = head
        count = 0
        while p.next:
            p = p.next
            count += 1
        return count

    hx, hy = x.head, y.head
    len_x, len_y = get_length(hx), get_length(hy)
    if len_x > len_y:
        for _ in range(len_x - len_y):
            hx = hx.next
    else:
        for _ in range(len_y - len_x):
            hy = hy.next

    while hx and hy:
        if hx == hy:
            return hx.value
        hx = hx.next
        hy = hy.next

    return None


if __name__ == '__main__':
    link = LinkList(list(range(10)))
    link.display()

    # delete node
    delete_node(link, link.head.next)
    link.display()

    # reverse link
    reverse_link(link.head)
    link.display()

    # the k-th last value
    print(last_k_node(link.head, 3))

    # middle node
    print(middle_node(link.head))

    # has circle
    print(has_circle(link.head))
    link.head.next.next.next.next = link.head.next.next
    print(has_circle(link.head))

    # entrance of circle
    print(entrance_of_circle(link.head))

    l1 = LinkList([1, 2, 3])
    l2 = LinkList([4, 5, 6, 7])
    intersection = LinkList([8, 9])
    p = l1.head
    while p.next:
        p = p.next
    p.next = intersection.head.next
    p = l2.head
    while p.next:
        p = p.next
    p.next = intersection.head.next
    l1.display()
    l2.display()

    # is intersect(no circle)
    print(has_intersect(l1, l2))
    print(first_common_node(l1, l2))

    # is intersect(with circle)
    intersection.head.next.next.next = intersection.head.next
    print(has_intersect_with_circle(l1, l2))