# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val = x# self.next = NoneclassSolution(object):defreorderList(self,head):""" :type head: ListNode :rtype: void Do not return anything, modify head in-place instead. """ifnothead:returnNoneslow=headfast=headwhilefastandfast.next:# split list into part1 and part2. 1-2,3-4;1-3,4-5.slow=slow.nextfast=fast.next.nextpart2=slow.nextslow.next=Nonepart1=headrevpart2=ListNode(0)# reverse part2whilepart2:tmp=ListNode(part2.val)tmp.next=revpart2.nextrevpart2.next=tmppart2=part2.nextrevpart2=revpart2.nextwhilerevpart2andpart1:# merge part1 and revpart2tmp=ListNode(revpart2.val)tmp.next=part1.nextpart1.next=tmppart1=part1.next.nextrevpart2=revpart2.next
近期评论