这是链表的第21题，力扣链接。

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

示例 1:

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

示例 2:

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

大致题意是偶数索引位置的节点左移，奇数位置的节点右移，然后两边的新链表拼接返回。

直接模拟一下返回：

func oddEvenList(head *ListNode) *ListNode {
	left, right := &ListNode{}, &ListNode{}
	leftCur, rightCur := left, right
	index := 0
	for ; head != nil; head = head.Next {
		if index%2 == 0 {
			leftCur.Next = &ListNode{Val: head.Val}
			leftCur = leftCur.Next
		} else {
			rightCur.Next = &ListNode{Val: head.Val}
			rightCur = rightCur.Next
		}
		index++
	}
	leftCur.Next = right.Next
	return left.Next
}

 当然，也可以原地移动：

func oddEvenList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	evenHead := head.Next
	odd := head
	even := evenHead
	for even != nil && even.Next != nil {
		odd.Next = even.Next
		odd = odd.Next
		even.Next = odd.Next
		even = even.Next
	}
	odd.Next = evenHead
	return head
}