ReOrder Linked List

Reorder the given singly-linked list N1 -> N2 -> N3 -> N4 -> … -> Nn -> null to be N1- > Nn -> N2 -> Nn-1 -> N3 -> Nn-2 -> … -> null

Examples

L = null, is reordered to null
L = 1 -> null, is reordered to 1 -> null
L = 1 -> 2 -> 3 -> 4 -> null, is reordered to 1 -> 4 -> 2 -> 3 -> null
L = 1 -> 2 -> 3 -> null, is reordred to 1 -> 3 -> 2 -> null

class Solution(object):
  def reorder(self, head):
    if not head or not head.next:
      return head
    head1,head2 = self.split(head)
    head3 = self.reverse(head2)
    head4 = self.merge(head1,head3)
    return head4
    
  def split(self,head):
    p = head
    q = ListNode(None)
    cur = head 
    length = 0
    while cur:
      cur = cur.next
      length += 1
    mid = length/2
    count = 1
    while p:
      if count == mid:
        q.next = p.next
        p.next = None
      p = p.next
      count += 1
    return head,q.next
  
  def reverse(self,head):
    p = head
    q = head.next
    while q:
      head.next = q.next
      q.next = p
      p = q
      q = head.next
    return p
  
  def merge(self,p,q):
    dummy = ListNode(None)
    dummy.next = p
    while p.next:
      cur1 = p.next
      cur2 = q.next
      p.next = q
      q.next = cur1
      p = cur1
      q = cur2
    p.next = q
    return dummy.next