Edit Distance @ LeetCode (Python)
Search in Rotated Sorted Array II @ LeetCode (Python)

Reorder List @ LeetCode (Python)

kitt posted @ 2014年4月08日 16:03 in LeetCode , 2582 阅读

先找到list的中点, 把后半部分reverse, 再merge前半部分list和后半部分list。

Find the middle node of the list, then reverse the second half of the list, then merge the first half list and the second half list.

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return nothing
    def reorderList(self, head):
        if head == None or head.next == None: return
        # find middle node
        fast = slow = head
        while True:
            if fast.next: fast = fast.next
            else: break
            if fast.next: fast, slow = fast.next, slow.next
            else: break
        # reverse the second half list
        prev, curr, head2, slow.next = slow.next, slow.next.next, slow.next, None
        while curr:
            prev.next, curr.next, head2 = curr.next, head2, curr 
            curr = prev.next
        # join the first half and the second half
        dummy2 = ListNode(0)
        dummy2.next, head2 = head2, dummy2 # add a dummy node to second half list
        prev1, curr1, prev2, curr2 = head, head.next, head2, head2.next
        while curr2:
            # insert curr2 node to first half list
            prev2.next, prev1.next, curr2.next = curr2.next, curr2, curr1 
            curr2 = prev2.next
            prev1 = curr1
            if prev1 == None: break
            curr1 = prev1.next

登录 *

loading captcha image...
or Ctrl+Enter