Reorder List

题目描述

解题方法

基本思想也不难，就是

• 找到List的中点，将原list分成两份 (一定要记得将前半部分的结尾设成None)
• 将后半部分reverse
• 然后再merge two list

Solution

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        if not head:
            return

        p1 = head
        p2 = head

        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next

        mid = p1.next
        p1.next = None # must set to None, otherwise the result would have a cycle

        # reverse second half
        pre = None
        cur = mid
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp

        q = pre
        p = head
        while p and q:
            tmp = q.next
            q.next = p.next
            p.next = q

            p = p.next.next
            q = tmp

Reference