一、题目
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就可以了。
