📑 题目：143. 重排链表

🚀 本题 LeetCode 传送门

题目大意

按照指定规则重新排序链表：第一个元素和最后一个元素排列在一起，接着第二个元素和倒数第二个元素排在一起，接着第三个元素和倒数第三个元素排在一起。

解题思路

最近简单的方法是先把链表存储到数组里，然后找到链表中间的结点，按照规则拼接即可。这样时间复杂度是 O(n)，空间复杂度是 O(n)。

更好的做法是结合之前几道题的操作：链表逆序，找中间结点。

先找到链表的中间结点，然后利用逆序区间的操作，如 第 92 题 里的 reverseBetween() 操作，只不过这里的反转区间是从中点一直到末尾。最后利用 2 个指针，一个指向头结点，一个指向中间结点，开始拼接最终的结果。这种做法的时间复杂度是 O(n)，空间复杂度是 O(1)。

代码

package leetcode
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 解法一 单链表
func reorderList(head *ListNode) *ListNode {
 if head == nil || head.Next == nil {
  return head
 }
 // 寻找中间结点
 p1 := head
 p2 := head
 for p2.Next != nil && p2.Next.Next != nil {
  p1 = p1.Next
  p2 = p2.Next.Next
 }
 // 反转链表后半部分  1->2->3->4->5->6 to 1->2->3->6->5->4
 preMiddle := p1
 preCurrent := p1.Next
 for preCurrent.Next != nil {
  current := preCurrent.Next
  preCurrent.Next = current.Next
  current.Next = preMiddle.Next
  preMiddle.Next = current
 }
 // 重新拼接链表  1->2->3->6->5->4 to 1->6->2->5->3->4
 p1 = head
 p2 = preMiddle.Next
 for p1 != preMiddle {
  preMiddle.Next = p2.Next
  p2.Next = p1.Next
  p1.Next = p2
  p1 = p2.Next
  p2 = preMiddle.Next
 }
 return head
}
// 解法二 数组
func reorderList1(head *ListNode) *ListNode {
 array := listToArray(head)
 length := len(array)
 if length == 0 {
  return head
 }
 cur := head
 last := head
 for i := 0; i < len(array)/2; i++ {
  tmp := &ListNode{Val: array[length-1-i], Next: cur.Next}
  cur.Next = tmp
  cur = tmp.Next
  last = tmp
 }
 if length%2 == 0 {
  last.Next = nil
 } else {
  cur.Next = nil
 }
 return head
}
func listToArray(head *ListNode) []int {
 array := []int{}
 if head == nil {
  return array
 }
 cur := head
 for cur != nil {
  array = append(array, cur.Val)
  cur = cur.Next
 }
 return array
}