数据结构链表奇偶重排

### 链表奇偶重排的实现 链表的奇偶重排是一种常见的数据结构调整方法，其目标是将链表中的节点按照位置分为两部分：一部分由位于奇数位置上的节点组成，另一部分由位于偶数位置上的节点组成。最终的结果是一个新的链表，其中所有的奇数位置节点在前，偶数位置节点在后。 以下是基于给定引用内容和专业知识的具体实现： #### 算法思路 为了满足时间复杂度 \(O(n)\) 和空间复杂度 \(O(1)\)，可以通过以下方式完成： - 使用两个指针 `odd` 和 `even` 来分别追踪当前正在处理的奇数节点和偶数节点。 - 初始化时，`odd` 指向头节点（第一个奇数节点），而 `even` 则指向第二个节点（第一个偶数节点）。 - 同时记录偶数链表的头部 `evenHead`，以便后续将其连接到奇数链表的末尾。 - 迭代过程中交替调整 `odd.next` 和 `even.next` 的指向关系，从而逐步构建完整的奇数链表和偶数链表。 - 当遍历结束时，将偶数链表重新链接至奇数链表的末端[^2]。 #### Python 实现代码 下面是该算法的一个具体实现示例： ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def oddEvenList(head: ListNode) -> ListNode: if not head or not head.next: return head # 初始化奇数链表和偶数链表的相关变量 odd = head # 奇数链表的第一个节点 even = head.next # 偶数链表的第一个节点 evenHead = even # 记录偶数链表的起始点 while even and even.next: # 更新奇数链表的部分 odd.next = even.next # 将下一个奇数节点接到当前奇数节点后面 odd = odd.next # 移动到下一个奇数节点 # 更新偶数链表的部分 even.next = odd.next # 将下一个偶数节点接到当前偶数节点后面 even = even.next # 移动到下一个偶数节点 # 完成后将偶数链表接回奇数链表的末尾 odd.next = evenHead # 将偶数链表拼接到奇数链表之后 return head # 返回修改后的链表头节点 ``` #### 关键点解析 1. **边界条件** 如果输入链表为空 (`None`) 或仅有一个节点，则无需任何操作直接返回原链表即可[^1]。 2. **循环终止条件** 循环继续执行的前提是存在有效的偶数节点及其后续节点。当遇到 `even == None` 或者 `even.next == None` 时停止迭代[^2]。 3. **防止环形结构** 在某些情况下，如果未正确设置 `even.next = None`，可能会形成闭环。因此，在设计逻辑时需特别留意这一点[^1]。 4. **性能分析** 整个过程只需单次扫描整个列表来建立两条独立子链并最终合并它们，故总体时间为线性的 \(O(n)\)[^2]。由于只用了固定数量的额外存储单元用于保存临时状态信息，因而所需辅助内存也保持常量级别即 \(O(1)\)。 --- ###