题目

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:输入: head = [1,2,3,4] 输出: [1,4,2,3]

示例 2:输入: head = [1,2,3,4,5] 输出: [1,5,2,4,3]

提示：链表的长度范围为 [1, 5 * 104]

1 <= node.val <= 1000

注意：本题与主站 143 题相同

解题思路分析

1、数组辅助；时间复杂度O(n)，空间复杂度O(n)

func reorderList(head *ListNode)  {
   if head == nil || head.Next == nil {
      return
   }
   cur := head
   arr := make([]*ListNode, 0)
   for cur != nil {
      arr = append(arr, cur)
      cur = cur.Next
   }
   res := make([]*ListNode, 0)
   for i := 0; i < len(arr)/2; i++ {
      res = append(res, arr[i], arr[len(arr)-1-i])
   }
   if len(arr)%2 == 1 {
      res = append(res, arr[len(arr)/2])
   }
   cur = head
   for i := 1; i < len(res); i++ {
      cur.Next = res[i]
      cur = cur.Next
   }
   cur.Next = nil
}

2、反转链表；时间复杂度O(n)，空间复杂度O(1)

func reorderList(head *ListNode) {
   if head == nil || head.Next == nil {
      return
   }
   fast, slow := head, head
   for fast != nil && fast.Next != nil {
      fast = fast.Next.Next
      slow = slow.Next
   }
   second := reverse(slow.Next)
   slow.Next = nil
   cur := head
   count := 0
   for cur != nil && second != nil {
      a := cur.Next
      b := second.Next
      if count%2 == 0 {
         cur.Next = second
         cur = a
      } else {
         second.Next = cur
         second = b
      }
      count++
   }
}

func reverse(head *ListNode) *ListNode {
   var res *ListNode
   for head != nil {
      next := head.Next
      head.Next = res
      res = head
      head = next
   }
   return res
}

3、递归；时间复杂度O(n)，空间复杂度O(n)

func reorderList(head *ListNode) {
   if head == nil || head.Next == nil {
      return
   }
   length := 0
   cur := head
   for cur != nil {
      length++
      cur = cur.Next
   }
   helper(head, length)
}

func helper(head *ListNode, length int) *ListNode {
   if length == 1 {
      next := head.Next
      head.Next = nil
      return next
   }
   if length == 2 {
      next := head.Next.Next
      head.Next.Next = nil
      return next
   }
   tail := helper(head.Next, length-2)
   next := tail.Next
   temp := head.Next
   head.Next = tail
   tail.Next = temp
   return next
}

总结

Medium题目，题目同leetcode 143.重排链表