【leetcode】143. Reorder List解题报告

给定链表，让按照给的形式输出。
方法一：
把链表拆成两个部分，将第二个部分反转，然后再合并这两个链表
将拆分完的链表记做left和right，那么left要么和right相等要么比right多一个元素
该功能可以由下面的函数完成

		slow = head
        fast = head.next
        while (fast != None and fast.next != None):
            slow = slow.next
            fast = fast.next.next

这样slow的next就是right的头结点
因为是in-place式修改，所以先令头结点为left的第一个节点 ，然后再串上right的第一个节点然后再穿上right的第二个节点，如此往下。这样就将原来的左->右->左->右这样的顺序改成了右->左->右->左。拆分完后反转right链表并合并即可
AC代码，beat 60%

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reorderList(self, head):
        \"\"\"
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        \"\"\"
        if head == None or head.next == None:
            return 
        slow = head
        fast = head.next
        while (fast != None and fast.next != None):
            slow = slow.next
            fast = fast.next.next
       

        pNode = head
        right = slow.next
        slow.next =None
        left = head.next
        right  =self.reverse(right)



        while (left != None):
            pNode.next = right
            right = right.next
            pNode = pNode.next
            pNode.next = left
            pNode = pNode.next
            left = left.next
        pNode.next =right


    def reverse(self,root):

        pNode = root.next
        head = root
        head.next =None
        
        while(pNode):
            tmp = pNode
            pNode = pNode.next
            tmp.next = head
            head =tmp
        return head

方法二：
递归法
虽然说是不要返回任何值，但是递归没有return怎么结束呢，return指针就好了啊。但是该方法TTL了，仅学习使用

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

    def helper(self,head):
        if head == None or head.next == None:
            return head
        slow = head
        fast = head.next
        while(fast.next != None):
            slow = slow.next
            fast = fast.next
        slow.next = None
        print(slow.val)

        tmp =self.helper(head.next)
        head.next = fast
        head.next.next  = tmp
        return head