pylist

228. Middle of Linked List

Find the middle node of a linked list.

Example 1:

Input:  1->2->3
Output: 2	
Explanation: return the value of the middle node.

Example 2:

Input:  1->2
Output: 1	
Explanation: If the length of list is  even return the value of center left one.	

Challenge

If the linked list is in a data stream, can you find the middle without iterating the linked list again?

Solution

"""
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):
        # corner cases
        if head is None: # insane
            return None
        if head.next is None:
            return head
        # init 2 pointers
        slow = head
        fast = head.next
        # move pointers
        odd = True
        while True:
            if fast.next == None:
                return slow
            
            if odd:
                fast = fast.next
                slow = slow.next
            else:
                fast = fast.next
                
            odd = not odd

special care