Find the middle node in a singly linked list

Find the mid point (towards the end):

sample : 1-->2-->3 return 2 (for odd length of singly linked list,return the mid point)

sample : 1-->2-->3-->4 return 3 (for even length of singly linked list, return the first node of second-evenly-divided half)

Obviously you need to use runner's technique:

def findMid(head):
   if head == None or head.next == None:
        return head
   slow, fast = head, head
   while fast != None and fast.next != None:
       fast, slow = fast.next, slow.next
       if fast.next == None:
           break
       else:
           fast = fast.next

Find the mid point's previous node:

sample : 1-->2-->3 return 2 (for odd length of singly linked list,return the mid point)

sample : 1-->2-->3-->4 return 2 (for even length of singly linked list, return the last node of first-evenly-divided half)

Sometimes you want to divide a singly linked list into two halves and normally in this case, dividing means that you need to break the list into half, so it is crucial to get the node that is previous to the head node of the second half.

In the above case, after you get 2 from the first and second half sample, you need to set
prev.next = None

Until this is set, the break could be considered completed. On top of runner technique, you want to add a dummy node to the original head of the singly linked list, so that it returns the "previous node"

def findMid(head):
   if head == None or head.next == None:
        return head
   dummy = ListNode(0)
   dummy.next = head
   slow, fast = dummy, dummy
   while fast != None and fast.next != None:
       fast, slow = fast.next, slow.next
       if fast.next == None:
           break
       else:
           fast = fast.next