刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/reorder-list/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个单链表 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

思路

链表思维

这道题应该算是链表里一些基础思路的整合应用了。
看题意示例，应该是头部尾部交替选节点拼接，那其实整理下的话，那就是拆成三个步骤：

• 找到中点
• 反转后半部分
• 交替拼接

找中点，链表里没有下标，所以一般会用快慢指针，反转单调链表和拼接就都简单

链表指针操作容易迷糊的话，就画个图，会简单很多

数组思维

当然，跳出链表思维还有一个思路，那就是转化成数组，因为其实对于有下标的数组来说，这个头尾交替选点太简单不过了，所以就拿一个数组来承载节点，直接拼接就好，别忘了末尾指向nil
只是，空间复杂度会高些

至此，上代码

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    mid := findMidNode(head)
    head2 := reverse(mid.Next)
    mid.Next = nil
    for head2 != nil {
        next := head.Next
        next2 := head2.Next
        head.Next = head2
        head2.Next = next
        head = next
        head2 = next2
    }
}

func findMidNode(head *ListNode) *ListNode {
    fast, slow := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

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