class(object): def__init__(self, x): self.val = x self.next = None
classSolution(object): defreorderList(self, head): """ :type head: ListNode :rtype: void Do not return anything, modify head in-place instead. """ ifnot head ornot head.next: return
l = 0 cur = head while cur: l += 1 cur = cur.next m = (l - 1) / 2
cur = head for i in xrange(m): cur = cur.next
head2 = cur.next cur.next = None
# now we have two lists, reverse the second one prev = head2 cur = head2.next prev.next = None while cur: next = cur.next cur.next = prev prev = cur cur = next head2 = prev
# then we merge the two lists while head2: n1 = head.next n2 = head2.next head.next = head2 head2.next = n1 head = n1 head2 = n2
近期评论