LintCode: Middle of Linked List

## https://code.dennyzhang.com/middle-of-linked-list
## Basic Ideas: fast/slow pointers
## Complexity: Time O(n), Space O(1)
"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""


class Solution:
    """
    @param: head: the head of linked list.
    @return: a middle node of the linked list
    """
    def middleNode(self, head):
        slow, fast = head, head
        while fast and fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow