easy understand python solution with comments


  • 0

    The reverse and partionlist functions can be applied to other related questions. The main idea is:

    • Split the list into two parts, the left part can be one more element than right part if the total length is odd.
    • Reverse the right part.
    • Moving two pointers to merge the two parts. You can imagine it rebuilds a link.
       def reverse(self, head):
            if not head or not head.next:
                return head
            pre=None
            cur=head
            while cur:
                # record the value before it change
                next=cur.next
                cur.next=pre
                pre=cur
                cur=next
            return pre
        
        def partionlist(self,head):
            if not head or not head.next:
                return head
            slow=head
            fast=head.next.next
            while fast and fast.next:
                slow=slow.next
                fast=fast.next.next
                
            # make sure the left is 1 more than right part if odd
            if fast:
                fast=slow.next.next
                slow.next.next=None
            else:
                fast=slow.next
                slow.next=None
            return fast
            
        def reorderList(self, head):
            if not head or not head.next:
                return
            # first partion list
            right=self.partionlist(head)
            # reverse the right part
            reverse=self.reverse(right)
            
            p=head
            q=reverse
            while p and q:
                # record the next possible value
                nextp=p.next
                nextq=q.next
                # change the link
                p.next=q
                q.next=nextp
                # move on
                p=nextp
                q=nextq
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.