一、题目

Reorder List

二、解题

把链表组成一个环状，1,2,3,4->1,4,2,3

• 定义两个方向的指针，第一个方向从头往后，从1指向9
• 第二个指针，定义一个方法findLast，遍历一遍找到上一个指针，从8指向1的下一个2
• 最后注意偶数和奇数个数的操作有些许不同。

三、尝试与结果

class Solution(object):
    def findLast(self,last):
        t = last
        while last.next != t:
            last = last.next
        return last

    def reorderList(self, head):
        if head == None:
            return None
        if head.next == None:
            return head

        p = head
        while p.next != None:
            p = p.next
        last = p

        p = head
        while p.next != last and p != last:
            q = p
            p = p.next  
            q.next = last
            last.next = p
            last = self.findLast(last)
        
        if p.next == last:
            p.next = last
            last.next = None

        if p == last:
            last.next = None

        while head != None:
            head = head.next
        return head

结果：TL，是能够解出答案的，但是时间复杂度是O（n^2）

四、学习与记录

根据提示，把链表分成两部分，然后后半部分翻转插入。

class Solution(object):
    def reorderList(self, head):
        if head == None:
            return None
        if head.next == None:
            return 

        fast = head
        slow = head

        # 快慢指针找中点
        while (fast.next != None and fast.next.next != None):
            fast = fast.next.next
            slow = slow.next
        
        front = slow.next
        slow.next = None

        # 链表的反向
        last = None
        mid = None
        while front.next != None:
            mid = front
            front = front.next
            mid.next = last
            last = mid

        front.next = mid


        # 链表的合并插入(front 和head的合并插入)
        first = head
        result = first
        second = front
        while first.next != None:
            temp = first
            first = first.next
            temp.next = second
            temp = temp.next
            second = second.next
            temp.next = first

        if second != None:
            first.next = second
        
        head = result
        return 

结果：AC

找中点使用的是快慢指针
反向使用了三个指针
合并采用了归并

最后有个坑，返回值不是要结果链表的头，而是直接赋值给head就可以了。