### 问题描述

```给定链表 1->2->3->4, 重新排列为 1->4->2->3.
```

```给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
```

### 解题思路

• 通过快慢指针，找到中间节点
• 将 list 从中间一分为二
• 将右面的子 list 反转
• 将右面的子列表插入到左面的列表的“缝隙”中

### Python 实现

```# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
def print_list(self, p):
if p is None:
return
temp = p
while temp is not None:
print(temp.val)
temp = temp.next

def revserve(self, node):
if node is None or node.next is None:
return node

p1 = node
p2 = node.next
p1.next = None
while p2 is not None:
p3 = p2.next
p2.next = p1
p1 = p2
p2 = p3

return p1

"""
"""

# find the middle node using fast and slow pointer
while fast is not None and \
fast.next is not None and \
fast.next.next is not None:
slow = slow.next
fast = fast.next.next

# split the list into two lists
p2 = slow.next
slow.next = None
# reverse the second list using three pointer method
p2 = self.revserve(p2)

# insert into the grap
while p2 is not None:
p1_next = p1.next
p1.next = p2
p2_next = p2.next
p2.next = p1_next

p1 = p1_next
p2 = p2_next

```