Python solution with stack reverse second half


  • 0
    J
    class Solution(object):
        def reorderList(self, head):
            if head == None or head.next == None:
                return 
            
            pre = slow = fast = head
            
            while fast and fast.next:
                pre = slow
                slow = slow.next
                fast = fast.next.next
                
            pre.next = None
            
            stk = []
            while slow:
                stk.append(slow)
                slow = slow.next
            
            pt = head
            
            while stk and pt:
                node = stk.pop()
                node.next = None
                
                if pt.next == None:
                    pt.next = node
                    pt = pt.next
                    break
                else:
                    node.next = pt.next
                    pt.next = node
                    pt = pt.next.next
            
            if stk:
                node = stk.pop()
                node.next = None
                pt.next = node
    

Log in to reply
 

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