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.Next
        odd = odd.Next
        
        // 将下一个偶数节点链接到偶数链表尾部
        even.Next = odd.Next
        even = even.Next
    }
    
    // 将偶数链表接在奇数链表尾部
    odd.Next = evenHead
    return head
}

二、算法分析

1. 核心思路

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

2. 关键步骤

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

3. 复杂度

三、图解示例

四、边界条件与扩展

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 head
        odd, even, even_head = head, head.next, head.next
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = even_head
        return 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. 工程优化方向

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