LeetCode 328. 奇偶链表

 LeetCode 328. 奇偶链表

给定单链表的头节点 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]

提示:

• n == 链表中的节点数
• 0 <= n <= 104
• -106 <= Node.val <= 106

思路：

1. 用两个奇偶指针分别指向奇偶节点的起始位置，另外需要一个单独的指针even_head来保存偶节点的起点位置;
2. 然后把奇节点的指向偶节点的下一个(一定是奇节点)，此奇节点后移一步;
3. 再把偶节点指向下一个奇节点的下一个(一定是偶节点)，此偶节点后移一步，以此类推直至末尾;
4. 此时把分开的偶节点的链表连在奇节点的链表后即可.

时间复杂度：O(N)

空间复杂度：O(1)

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/funcoddEvenList(head*ListNode) *ListNode {
ifhead==nil {
returnnil    }
pOdd, pEven :=head, head.NexthEven :=head.Next// 保存首个偶数节点的位置，便于最后拼接forpEven!=nil&&pEven.Next!=nil {
pOdd.Next=pEven.NextpOdd=pOdd.NextpEven.Next=pOdd.NextpEven=pEven.Next    }
pOdd.Next=hEvenreturnhead}