给定一个包含6个节点的链表1-2-3-4-5-6，重排为1-6-2-5-3-4，即首尾交替连接。请实现该算法并分析时间和空间复杂度。

Question

给定一个包含6个节点的链表1->2->3->4->5->6，重排为1->6->2->5->3->4，即首尾交替连接。请实现该算法并分析时间和空间复杂度。

Accepted Answer

考察点：考察链表操作、快慢指针和反转链表的基本功。回答思路：正确识别并划分链表的前半部分和后半部分 使用快慢指针找到链表的中点 反转后半部分链表并正确交替合并两段 分析时间复杂度O(n)和空间复杂度O(1)

给定一个包含6个节点的链表1->2->3->4->5->6，重排为1->6->2->5->3->4，即首尾交替连接。请实现该算法并分析时间和空间复杂度。