给定一个单链表 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 * 10^4]
- 1 <= node.val <= 1000
解题：
func reorderList(head *ListNode) {
var stack []*ListNode
for head != nil {
stack = append(stack, head)
head = head.Next
}
start := &ListNode{Next: nil}
head = start
for len(stack) > 0 {
start.Next = stack[0]
start = start.Next
stack = stack[1:]
l := len(stack)
if l > 0 {
start.Next = stack[l-1]
start = start.Next
stack = stack[:l-1]
}
}
start.Next = nil
head = head.Next
}官方解答：
1.线性表
func reorderList(head *ListNode) {
if head == nil {
return
}
var nodes []*ListNode
for node := head; node != nil; node = node.Next {
nodes = append(nodes, node)
}
i, j := 0, len(nodes)-1
for i < j {
nodes[i].Next = nodes[j]
i++
if i == j {
break
}
nodes[j].Next = nodes[i]
j--
}
nodes[i].Next = nil
}2.寻找链表中点 + 链表逆序 + 合并链表
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func reverseList(head *ListNode) *ListNode {
var prev, cur *ListNode = nil, head
for cur != nil {
nextTmp := cur.Next
cur.Next = prev
prev = cur
cur = nextTmp
}
return prev
}
func mergeList(l1, l2 *ListNode) {
var l1Tmp, l2Tmp *ListNode
for l1 != nil && l2 != nil {
l1Tmp = l1.Next
l2Tmp = l2.Next
l1.Next = l2
l1 = l1Tmp
l2.Next = l1
l2 = l2Tmp
}
}
func reorderList(head *ListNode) {
if head == nil {
return
}
mid := middleNode(head)
l1 := head
l2 := mid.Next
mid.Next = nil
l2 = reverseList(l2)
mergeList(l1, l2)
}