LeetCode算法题(Go语言实现)_30

题目

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

一、代码实现

func oddEvenList(head *ListNode) *ListNode {if head == nil || head.Next == nil {return head}odd := head          // 奇数链表的当前尾节点even := head.Next    // 偶数链表的当前尾节点evenHead := even     // 保存偶数链表的头节点for even != nil && even.Next != nil {// 将下一个奇数节点链接到奇数链表尾部odd.Next = even.Nextodd = odd.Next// 将下一个偶数节点链接到偶数链表尾部even.Next = odd.Nexteven = even.Next}// 将偶数链表接在奇数链表尾部odd.Next = evenHeadreturn head
}

二、算法分析

1. 核心思路

• 双指针分离：使用两个指针 odd 和 even 分别追踪奇偶链表的尾部节点，通过交替连接实现原地修改
• 循环复用：在遍历过程中逐步构建奇偶链表，保持原始相对顺序
• 头节点保留：通过 evenHead 保存偶数链表头节点，最终合并链表时只需一次指针操作

2. 关键步骤

1. 初始化指针：odd 指向第一个节点（奇头），even 指向第二个节点（偶头）
2. 交替连接：
   • 将 odd 的下一个节点指向 even 的下一个节点（下一个奇数节点）
   • 将 even 的下一个节点指向新 odd 的下一个节点（下一个偶数节点）
3. 指针推进：odd 和 even 同步后移，继续构建各自的链表
4. 链表合并：将偶数链表头 evenHead 接在奇数链表尾部

3. 复杂度

指标	值	说明
时间复杂度	O(n)	单次遍历，每个节点访问一次
空间复杂度	O(1)	仅需固定数量的指针变量

三、图解示例

四、边界条件与扩展

1. 特殊场景验证

• 空链表：直接返回 nil
• 单节点链表：返回原链表（无需处理）
• 双节点链表：保持原顺序（奇数在前，偶数在后）
• 长交替链表：如 R-D-R-D → 分离后奇偶顺序保持不变

2. 多语言实现

# Python实现（原地修改）
class Solution:def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next:return headodd, even, even_head = head, head.next, head.nextwhile even and even.next:odd.next = even.nextodd = odd.nexteven.next = odd.nexteven = even.nextodd.next = even_headreturn head

// Java实现（指针同步移动）
class Solution {public ListNode oddEvenList(ListNode head) {if (head == null || head.next == null) return head;ListNode odd = head, even = head.next, evenHead = even;while (even != null && even.next != null) {odd.next = even.next;odd = odd.next;even.next = odd.next;even = even.next;}odd.next = evenHead;return head;}
}

五、总结与扩展

1. 核心创新点

• 链式跳跃：通过 odd.next = even.next 直接跳过偶数节点，避免多次遍历
• 数学归纳法证明：奇数节点的下一个节点总是偶数节点的下一个节点，确保正确性

2. 扩展应用

• 多级分离：扩展为分离模3余数不同的节点（如余0、1、2）
• 双向链表：修改指针操作逻辑支持双向遍历
• 环形链表检测：结合快慢指针检测环的存在

3. 工程优化方向

• 内存预分配：预先计算链表长度优化指针操作
• 并发安全：添加锁机制支持多线程环境下的链表操作