I tested this solution on my computer and it seems to be giving the correct answer. I am using the "1) find mid 2) reverse 3) merge" approach. Can anybody provide any insight?
def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ if not head or not head.next: return head prev = None cur = head nxt = cur.next while cur: cur.next = prev prev = cur if not nxt: break cur = nxt nxt = nxt.next return cur def reorderList(self, head): """ :type head: ListNode :rtype: void Do not return anything, modify head in-place instead. """ if not head: return head if not head.next: # 1 node, no change return head if not head.next.next: # 2 nodes, no change return head oneStep = head twoStep = head while twoStep.next and twoStep.next.next: oneStep = oneStep.next twoStep = twoStep.next.next curMid = self.reverseList(oneStep.next) cur = head oneStep.next = curMid while curMid: tmp = cur.next tmp2 = curMid.next cur.next = curMid curMid.next = tmp cur = tmp curMid = tmp2