LeetCode 第328题：奇偶链表

📖 文章摘要

本文详细解析LeetCode第328题“奇偶链表”，这是一道中等难度的链表操作问题。文章提供了双指针解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升链表操作能力的程序员。

核心知识点： 链表、双指针、指针操作
难度等级： 中等
推荐人群： 具有基础数据结构知识，想要提升链表操作能力的程序员

题目描述

给定单链表的头节点 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 <= 10^4
-10^6 <= Node.val <= 10^6

解题思路

方法：双指针

使用两个指针分别处理奇数位置和偶数位置的节点。

关键点：

使用两个指针分别指向奇数节点和偶数节点
保存偶数链表的头节点
正确处理链表的连接关系
处理边界情况

具体步骤：

处理特殊情况（空链表或只有一个节点）
初始化奇数指针和偶数指针
保存偶数链表的头节点
遍历链表，重新连接节点
将奇数链表与偶数链表连接

时间复杂度：O(n) 空间复杂度：O(1)

图解思路

链表重排过程表

步骤	奇数链表	偶数链表	当前操作
初始	1->2->3->4->5	null	分离开始
1	1->3	2->4	前两组分离
2	1->3->5	2->4	处理最后节点
3	1->3->5->2->4	null	连接两个链表

指针移动示意图

1 -> 2 -> 3 -> 4 -> 5
odd  even
     |
     v
1 -> 3 -> 4 -> 5
|    odd  even
v
最终：1 -> 3 -> 5 -> 2 -> 4

代码实现

C# 实现

public class Solution {
    public ListNode OddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // 初始化奇偶指针
        ListNode odd = head;
        ListNode even = head.next;
        ListNode 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;
    }
}

Python 实现

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        # 初始化奇偶指针
        odd = head
        even = head.next
        even_head = even
        
        # 重新连接节点
        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

C++ 实现

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        // 初始化奇偶指针
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;
        
        // 重新连接节点
        while (even && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        
        // 连接奇偶链表
        odd->next = evenHead;
        
        return head;
    }
};

执行结果

C# 实现

执行用时：88 ms
内存消耗：38.2 MB

Python 实现

执行用时：44 ms
内存消耗：16.8 MB

C++ 实现

执行用时：12 ms
内存消耗：10.4 MB

性能对比

语言	执行用时	内存消耗	特点
C#	88 ms	38.2 MB	实现简洁，性能适中
Python	44 ms	16.8 MB	代码最简洁
C++	12 ms	10.4 MB	性能最优

代码亮点

🎯 使用双指针高效处理链表
💡 空间复杂度为O(1)
🔍 完整处理边界情况
🎨 代码结构清晰，易于理解

常见错误分析

🚫 没有保存偶数链表的头节点
🚫 指针移动顺序错误
🚫 边界条件判断不当
🚫 链表连接顺序错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
双指针	O(n)	O(1)	空间效率高	需要注意指针操作
数组辅助	O(n)	O(n)	实现简单	空间复杂度高

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第328题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

方法：双指针

图解思路

链表重排过程表

指针移动示意图

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流