3 Steps Python code sharing


  • 0
    O

    Just share the Python code using 3 steps methods.
    If you can't get it, strongly recommend to draw it down,
    and think how to change the links regarding the code!

    def reorderList(self, head):
    	if not head or not head.next or not head.next.next:
    		return
    	head2 = self.findMid(head)
    	head2 = self.reverseList(head2)
    	self.zigZagMerge(head, head2)
    
    def findMid(self, head):
    	# step1: separate list to two parts
    	# ex: "1-2-3-4-5" ==> return head2 would be 4
    	slow, fast = head, head.next
    	while fast:
    		slow = slow.next
    		fast = fast.next.next if fast.next else None
    	head2, slow.next = slow.next, None
    	return head2
    
    def reverseList(self, head):
    	# step2: reverse the second half part
    	# ex: following step1, second list "4-5" would become "5-4" 	
    	pre, cur = head, head.next
    	while cur:
    		tmp, cur.next = cur.next, pre
    		pre, cur = cur, tmp
    	head.next = None
    	return pre
    
    def zigZagMerge(self, head, head2):
    	# step3: merging
    	# l1 = "1 2 3"
    
    	# l2 =  "5 4"
    	# connect these two are like drawing a zig zag
    	cur1, cur2 = head, head2
    	while cur2:
    		tmp1, tmp2 = cur1.next, cur2.next
    		cur1.next, cur2.next = cur2, tmp1
    		cur1, cur2 = tmp1, tmp2

Log in to reply
 

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